Cube intersection concepts in median graphsBrešar, Boštjan (Avtor) Kraner Šumenjak, Tadeja (Avtor) matematikateorija grafovkartezični produktmedianski grafgraf kockpresečni grafkonveksnostmathematicsgraph theoryCartesian productmedian graphcube graphintersection graphconvexityObravnavamo 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.20092015-07-10 15:08:54Delo ni kategorizirano51791sl