20.500.12556/DKUM-51791 Cube intersection concepts in median graphs Presečni koncepti kock v medianskih grafih 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. 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. 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 true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 15:08:54 2015-07-10 15:08:54 2022-05-30 03:07:24 2019-07-11 07:28:25 2009 0 0 str. 2990-2997 iss. 10 Vol. 309 2009 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 1118479 15167065 0012-365X URN:SI:UM:DK:XIOAADIY http://dx.doi.org/10.1016/j.disc.2008.07.032 1 https://dk.um.si/Dokument.php?lang=slv&id=76351 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0