VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • On the chromatic edge stability index of graphs
    Akbari, Saieed ...
    Naj bo dan netrivialen graf ▫$G$▫. Najmanjša kardinalnost takšne množice povezav ▫$F$▫ grafa ▫$G$▫, za katero velja ▫$\chi'(G \setminus F)<\chi'(G)$▫, imenujemo kromatični povezavni indeks ... stabilnosti grafa ▫$G$▫ in ga označimo z ▫$es_{\chi'}(G) (G)$▫; pri tem tako (najmanjšo) množico povezav ▫$F$▫ imenujemo (najmanjša) ublažitvena množica. Očitno za poljuben graf ▫$G$▫ velja ▫$1\le es_{\chi'}(G) \le \lfloor n/2\rfloor$▫, v članku pa raziščemo grafe, ki zavzamejo ekstremne in skoraj ekstremne vrednosti ▫$es_{\chi'}(G)$▫ v omenjenih neenakostih. Klasificiramo tiste grafe ▫$G$▫, za katere velja ▫$es_{\chi'}(G)=\lfloor n/2\rfloor$▫ in okarakteriziramo tiste grafe ▫$G$▫, za katere je ▫$es_{\chi'}(G)=\lfloor n/2\rfloor-1$▫ in ▫$\chi'(G)=\Delta(G)+1$▫. Ugotovimo, da so lihi cikli in graf ▫$K_2$▫ natanko vsi regularni povezani grafi, ki imajo kromatični indeks stabilnosti enak ▫$1$▫; po drugi strani dokažemo, da je problem preveritve, ali graf ▫$G$▫ zadošča ▫$es_{\chi'}(G)=1$▫, NP-težek problem. Prav tako dokažemo, da je vsaka najmanjša ublažitvena množica v ▫$r$▫-regularnem grafu ▫$G$▫, kjer je ▫$r\ne 4$▫ in je ▫$es_{\chi'}(G)=2$▫, prirejanje. Nadalje zastavimo domnevo, da za vsak graf ▫$G$▫ obstaja najmanjša ublažitvena množica, ki je prirejanje in domnevo dokažemo v primeru, ko graf ▫$G$▫ zadošča ▫$es_{\chi'}(G)\in\{1,2,\lfloor n/2\rfloor-1,\lfloor n/2\rfloor\}$▫ in ko je ▫$G$▫ dvodelen graf.
    Vir: European journal of combinatorics = Journal européen de combinatoire = Europäische Zeitschrift für Kombinatorik. - ISSN 0195-6698 (Vol. 111, June 2023, art. 103690 (16 str.))
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2023
    Jezik - angleški
    COBISS.SI-ID - 156875267

    Povezava(-e):

    https://www.sciencedirect.com/science/article/pii/S0195669823000070
    DOI

Vnos na polico