ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • Spectrally degenerate graphs: Hereditary case
    Dvořák, Zdeněk ; Mohar, Bojan, 1956-
    Znano je, da spektralni radij drevesa maksimalne stopnje ▫$\Delta$▫ nikoli ne presega vrednosti ▫$2\sqrt{\Delta-1}$▫. Znana je tudi posplošitev tega dejstva na poljubne ravninske grafe in na ... ▫$d$▫-degenerirane grafe. Ti rezultati so motivacija za uvedbo novega parametra. Pravimo, da je graf ▫$G$▫ spektralno ▫$d$▫-degeneriran, kadar ima vsak njegov podgraf ▫$H$▫ spektralni radij manjši od ▫$\sqrt{d\Delta(H)}$▫. Dokazan je šibki obrat zgoraj omenjenih rezultatov, ki pove, da ima vsak spektralno ▫$d$▫-degeneriran graf ▫$G$▫ vozlišče, ki je stopnje kvečjemu ▫$4d\log_2(\Delta(G)/d)$▫ (če je ▫$\Delta(G) \ge 2d$▫). V tej oceni se odvisnosti od ▫$\Delta$▫ ne da odpraviti, kar je dokazano z verjetnostno konstrukcijo posebnih primerov. Dokazano je tudi, da je odločitveni problem, ali je dani graf spektralno ▫$d$▫-degeneriran, co-NP-poln.
    Source: Journal of combinatorial theory. Series B. - ISSN 0095-8956 (Vol. 102, iss. 5, 2012, str. 1099-1109)
    Type of material - article, component part
    Publish date - 2012
    Language - english
    COBISS.SI-ID - 16410457

    Link(s):

    http://dx.doi.org/10.1016/j.jctb.2012.05.002

Shelf entry