Cube intersection concepts in median graphs

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

Povzetek

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.

Ključne besede

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;

Podatki

Jezik:	Angleški jezik
Leto izida:	2009
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FKBV - Fakulteta za kmetijstvo in biosistemske vede
UDK:	519.17
COBISS:	15167065
ISSN:	0012-365X
Št. ogledov:	775
Št. prenosov:	92
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarni naslov:	Presečni koncepti kock v medianskih grafih
Sekundarni povzetek:	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.
Sekundarne ključne besede:	matematika;teorija grafov;kartezični produkt;medianski graf;graf kock;presečni graf;konveksnost;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 2990-2997
Letnik:	ǂVol. ǂ309
Zvezek:	ǂiss. ǂ10
Čas izdaje:	2009
ID:	1474305