VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • The 4/5 upper bound on the game total domination number
    Henning, Michael A. ; Klavžar, Sandi ; Rall, Douglas F.
    Raziskovana je nedavno vpeljana celotna igra dominacije. To igro igrata na grafu ▫$G$▫ dva igralca, ki sta poimenovana Dominator in Zavlačevalka. Igralca izmenoma izbirata vozlišča grafa tako, da ... vsako izbrano vozlišče celotno dominira vsaj eno vozlišče, ki ni bilo celotno dominirano s prej izbranimi vozlišči. Dominatorjev cilj je kar se da hitro celotno dominirati graf graf ▫$G$▫, medtem ko želi Zavlačevalka kar se da zakasniti ta postopek. Celotno igralno dominacijsko število ▫$\gamma_{tg}(G)$▫ grafa ▫$G$▫ je število potez, ki jih opravita igralca, če igro začne Dominator in oba igralca igrata optimalno. Kadar Zavlačevalka začne igro, ustrezno invarianto označimo z ▫$\gamma_{tg}'(G)$▫. V članku je dokazano, da če je ▫$G$▫ graf na ▫$n$▫ vozliščih, v katerem vsaka komponenta vsebuje vsaj tri vozlišča, potem velja ▫$\gamma_{tg}(G) \le 4n/5$▫ in ▫$\gamma_{tg}'(G) \le (4n+2)/5$▫. Kot posledico tega rezultata dobimo tudi zgornji meji za obe igri na grafih, ki so brez izoliranih vozlišč.
    Vir: Combinatorica. - ISSN 0209-9683 (Vol. 37, iss. 2, 2017, str. 223-251)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2017
    Jezik - angleški
    COBISS.SI-ID - 18018137

    Povezava(-e):

    http://dx.doi.org/10.1007/s00493-015-3316-3

vir: Combinatorica. - ISSN 0209-9683 (Vol. 37, iss. 2, 2017, str. 223-251)
loading ...
loading ...
loading ...

Vnos na polico