DIKUL - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • Cube intersection concepts in median graphs
    Brešar, Boštjan ; Kraner Šumenjak, Tadeja
    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.
    Vir: Discrete mathematics. - ISSN 0012-365X (Vol. 309, iss. 10, 2009, str. 2990-2997)
    Vrsta gradiva - članek, sestavni del
    Leto - 2009
    Jezik - angleški
    COBISS.SI-ID - 15167065

    Povezava(-e):

    http://dx.doi.org/10.1016/j.disc.2008.07.032
    Digitalna knjižnica Univerze v Mariboru – DKUM

vir: Discrete mathematics. - ISSN 0012-365X (Vol. 309, iss. 10, 2009, str. 2990-2997)

loading ...
loading ...
loading ...

Vnos na polico