VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
PDF
  • Grundy domination and zero forcing in regular graphs
    Brešar, Boštjan ; Brezovnik, Simon, 1992-
    Za dani končni graf ▫$G$▫, maksimalno dolžino takega zaporedja ▫$(v_1,\ldots,v_k)$▫ vozlišč grafa ▫$G$▫, v katerem vsak ▫$v_i$▫ dominira vozlišče, ki ni bilo dominirano s strani vozlišč množice ... ▫$\{v_1,\ldots,v_{i-1}\}$▫, imenujemo Grundyjevo dominantno število grafa ▫$G$▫ in ga označimo z ▫$\gamma_{\rm gr}(G)$▫. Z majhno modifikacijo te definicije dobimo Z-Grundyjevo dominantno število grafa, ki predstavlja dualno invarianto dobro znanemu številu ničelne prisile. V članku dokažemo, da za vsak povezan ▫$k$▫-regularen graf ▫$G$▫, ki ni eden od grafov ▫$K_{k+1}$▫ oz. ▫$\overline{2C_4}$▫, velja ▫$\gamma_{\rm gr}(G) \ge \frac{n + \lceil \frac{k}{2} \rceil - 2}{k-1}$▫, kjer je ▫$n$▫ red grafa ▫$G$▫. V primeru, ko je ▫$k=3$▫, se meja poenostavi v mejo ▫$\gamma_{\rm gr}(G) \geq \frac{n}{2}$▫ in v članku okarakteriziramo vse kubične grafe, za katere velja ▫$\gamma_{\rm gr}(G)=\frac{n}{2}$▫. Če ▫$G$▫ ni ▫$K_4$▫ niti ▫$K_{3,3}$▫, potem je ▫$\frac{n}{2}$▫ tudi zgornja meja za število ničelne prisile povezanega kubičnega grafa in v članku okarakteriziramo kubične povezane grafe, ki to mejo dosežejo.
    Vir: Bulletin of the Malaysian Mathematical Sciences Society. - ISSN 0126-6705 (Vol. 44, iss. 6, Nov. 2021, str. 3637-3661)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2021
    Jezik - angleški
    COBISS.SI-ID - 79823363

    Povezava(-e):

    https://link.springer.com/article/10.1007%2Fs40840-021-01134-7
    DOI

Vnos na polico