Crossing graphs of fiber-complemented graphs

Boštjan Brešar (Avtor), Aleksandra Tepeh (Avtor)

Povzetek

Grafi zastraženih inverzov tvorijo obsežno nedvodelno posplošitev medianskih grafov. Z uporabo določenega naravnega barvanja povezav, ki je porojeno z relacijo vzporednosti med predvlakni grafov zastraženih inverzov, vpeljemo križni graf grafa zastraženega inverza ▫$G$▫ kot graf, katerega vozlišča so barve, dve barvi pa sta sosednji, če se križata na kakem induciranem 4-ciklu v grafu ▫$G$▫. V članku pokažemo, da je graf zastraženega inverza 2-povezan natanko tedaj, ko je njegov križni graf povezan. Karakteriziramo tiste grafe zastraženih inverzov, ki imajo poln križni graf pa tudi tiste s tetivnim križnim grafom.

Ključne besede

matematika;teorija grafov;medianski grafi;zastražene množice;predvlakna;kartezični produkt grafov;ekspanzija;mathematics;graph theory;median graphs;gated sets;prefibers;kartezični produkti;expansion;

Podatki

Jezik:	Angleški jezik
Leto izida:	2008
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK:	519.17
COBISS:	14520665
ISSN:	0012-365X
Št. ogledov:	51
Št. prenosov:	25
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Križni grafi grafov zastraženih inverzov
Sekundarni povzetek:	Fiber-complemented graphs form a vast non-bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph ▫$G$▫ as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in ▫$G$▫. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.
Sekundarne ključne besede:	matematika;teorija grafov;medianski grafi;zastražene množice;predvlakna;kartezični produkt grafov;ekspanzija;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1176-1184
Letnik:	ǂVol. ǂ308
Zvezek:	ǂiss. ǂ7
Čas izdaje:	2008
ID:	1473264