Crossing graphs of fiber-complemented graphs

Brešar, Boštjan; Tepeh, Aleksandra

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Crossing graphs of fiber-complemented graphs
Authors:	ID Brešar, Boštjan (Author) ID Tepeh, Aleksandra (Author)
Files:	http://dx.doi.org/10.1016/j.disc.2007.04.005
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	FERI - Faculty of Electrical Engineering and Computer Science
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
Year of publishing:	2008
Number of pages:	str. 1176-1184
Numbering:	Vol. 308, iss. 7
PID:	20.500.12556/DKUM-51605
UDC:	519.17
ISSN on article:	0012-365X
COBISS.SI-ID:	14520665
NUK URN:	URN:SI:UM:DK:OJI2DV3T
Publication date in DKUM:	10.07.2015
Views:	1422
Downloads:	94
Metadata:
Categories:	Misc.
:	BREŠAR, Boštjan and TEPEH, Aleksandra, 2008, Crossing graphs of fiber-complemented graphs. Discrete mathematics [online]. 2008. Vol. 308, no. 7, p. 1176–1184. [Accessed 31 March 2025]. Retrieved from: http://dx.doi.org/10.1016/j.disc.2007.04.005 Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Similar works from our repository:

Similar works from other repositories:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:	Discrete mathematics
Shortened title:	Discrete math.
Publisher:	North-Holland
ISSN:	0012-365X
COBISS.SI-ID:	1118479

Secondary language

Language:	Unknown
Title:	Križni grafi grafov zastraženih inverzov
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.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back