Cube intersection concepts in median graphs

Boštjan Brešar (Author), Tadeja Kraner Šumenjak (Author)

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;

Data

Language:	English
Year of publishing:	2009
Typology:	1.01 - Original Scientific Article
Organization:	UM FKBV - Faculty of Agriculture
UDC:	519.17
COBISS:	15167065
ISSN:	0012-365X
Views:	775
Downloads:	92
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Unknown
Secondary title:	Presečni koncepti kock v medianskih grafih
Secondary 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.
Secondary keywords:	matematika;teorija grafov;kartezični produkt;medianski graf;graf kock;presečni graf;konveksnost;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 2990-2997
Volume:	ǂVol. ǂ309
Issue:	ǂiss. ǂ10
Chronology:	2009
ID:	1474305