Povzetek

Skoraj medianski grafi in semi-medianski grafi sta dve naravni posplošitvi dobro znanega razreda medianskih grafov. V članku dokažemo, da je semi-medianski graf skoraj medianski, če in samo če ne vsebuje konveksnega cikla dolžine večje kot štiri.

Ključne besede

matematika;teorija grafov;medianski graf;konveksen cikel;delna kocka;mathematics;graf theory;median graph;convex cycle;partial cube;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK: 519.17
COBISS: 14253401 Povezava se bo odprla v novem oknu
ISSN: 0195-6698
Št. ogledov: 38
Št. prenosov: 19
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Neznan jezik
Sekundarni naslov: Karakterizacija skoraj medianskih grafov
Sekundarni povzetek: Almost-median and semi-median graphs are two natural generalizations of the well-known class of median graphs. In this note we prove that a semi-median graph is almost-median if and only if it does not contain any convex cycle of length greater than four.
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: str. 916-920
Letnik: ǂVol. ǂ28
Zvezek: ǂno. ǂ3
Čas izdaje: 2007
ID: 1473042