Crossing graphs of fiber-complemented graphs

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

Abstract

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.

Keywords

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;

Data

Language:	English
Year of publishing:	2008
Typology:	1.01 - Original Scientific Article
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
UDC:	519.17
COBISS:	14520665
ISSN:	0012-365X
Views:	51
Downloads:	25
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Križni grafi grafov zastraženih inverzov
Secondary abstract:	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.
Secondary keywords:	matematika;teorija grafov;medianski grafi;zastražene množice;predvlakna;kartezični produkt grafov;ekspanzija;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 1176-1184
Volume:	ǂVol. ǂ308
Issue:	ǂiss. ǂ7
Chronology:	2008
ID:	1473264