Cube intersection concepts in median graphs

Brešar, Boštjan; Kraner Šumenjak, Tadeja

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Cube intersection concepts in median graphs
Authors:	ID Brešar, Boštjan (Author) ID Kraner Šumenjak, Tadeja (Author)
Files:	http://dx.doi.org/10.1016/j.disc.2008.07.032
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	FERI - Faculty of Electrical Engineering and Computer Science
Abstract:	Obravnavamo različne razrede presečnih grafov maksimalnih hiperkock medianskih grafov. Za medianski graf ▫$G$▫ in celo število ▫$k ge 0$▫ je presečni graf ▫${mathcal{Q}}_k(G)$▫ definiran kot tisti graf, katerega vozlišča so maksimalne hiperkocke (z ozirom na inkluzijo) grafa ▫$G$▫ in sta dve vozlišči ▫$H_x$▫ in ▫$H_y$▫ v njem sosednji tedaj, ko presek ▫$H_x cap H_y$▫ vsebuje podgraf izomorfen ▫$Q_k$▫. V članku predstavimo karakterizacije kličnih grafov z uporabo omenjenih presečnih konceptov, ko je ▫$k>0$▫. Vpeljemo tudi t.i. maksimalno 2-presečni graf maksimalnih hiperkock medianskega grafa ▫$G$▫, ki ga označimo z ▫${mathcal{Q}}_{m2}(G)$▫ in predstavlja tisti graf, katerega vozlišča somaksimalne hiperkocke grafa ▫$G$▫, dve vozlišči v njem pa sta sosednji, če presek pripadajočih hiperkock ni strogo vsebovan v kakem preseku dveh maksimalnih hiperkock. Dokažemo, da je graf ▫$H$▫ brez induciranih diamantov, če in samo če obstaja takšen medianski graf ▫$G$▫, da je ▫$H$▫ izomorfen ▫${mathcal{Q}}_{m2}(G)$▫. Obravnavamo tudi konvergenco medianskega grafa h grafu na enem vozlišču glede na vse vpeljane operacije.
Keywords:	matematika, teorija grafov, kartezični produkt, medianski graf, graf kock, presečni graf, konveksnost, mathematics, graph theory, Cartesian product, median graph, cube graph, intersection graph, convexity
Year of publishing:	2009
Number of pages:	str. 2990-2997
Numbering:	Vol. 309, iss. 10
PID:	20.500.12556/DKUM-51791
UDC:	519.17
ISSN on article:	0012-365X
COBISS.SI-ID:	15167065
NUK URN:	URN:SI:UM:DK:XIOAADIY
Publication date in DKUM:	10.07.2015
Views:	1552
Downloads:	111
Metadata:
Categories:	Misc.
:	Copy citation

Average score:	(0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

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:	Presečni koncepti kock v medianskih grafih
Abstract:	We study different classes of intersection graphs of maximal hypercubes of median graphs. For a median graph ▫$G$▫ and ▫$k ge 0$▫, the intersection graph ▫${mathcal{Q}}_k(G)$▫ is defined as the graph whose vertices are maximal hypercubes (by inclusion) in ▫$G$▫, and two vertices ▫$H_x$▫ and ▫$H_y$▫ in ▫${mathcal{Q}}_k(G)$▫ are adjacent whenever the intersection ▫$H_x cap H_y$▫ contains a subgraph isomorphic to ▫$Q_k$▫. Characterizations of clique-graphs in terms of these intersection concepts when ▫$k>0$▫, are presented. Furthermore, we introduce the so-called maximal 2-intersection graph of maximal hypercubes of a median graph ▫$G$▫, denoted ▫${mathcal{Q}}_{m2}(G)$▫ whose vertices are maximal hypercubes of ▫$G$▫, and two vertices are adjacent if the intersection of the corresponding hypercubes is not a proper subcube of some intersection of two maximal hypercubes. We show that a graph ▫$H$▫ is diamond-free if and only if there exists a median graph ▫$G$▫ such that ▫$H$▫ is isomorphic to ▫${mathcal{Q}}_{m2}(G)$▫. We also study convergence of median graphs to the one-vertex graph with respect to all these operations.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back