FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • Total domination game played in forests [Elektronski vir]
    Henning, Michael A. ; Klavžar, Sandi ; Rall, Douglas F.
    Raziskovana je nedavno vpeljana celotna dominacijska igra. Igralca, Dominator in Zavlačevalka, izmenoma izbirata vozlišča grafa ▫$G$▫, tako da vsako izbrano vozlišče poveča množico celotno ... dominiranih vozlišč. Cilj Dominatorja je končati igro čim hitreje, medtem ko je Zavlačevalkin cilj ravno nasprotno. Celotno igralno dominacijsko število ▫$\gamma_{tg}(G)$▫ je skupno število izbranih vozlišč v igri, ko Dominator naredi prvo potezo in oba igralca igrata optimalno. V primeru, da igo začne Zavlačevalka, ustrezno invarianto označimo z ▫$\gamma_{tg}'(G)$▫. V tem članku je dokazalo, da če je ▫$F$▫ gozd na ▫$n$▫ vozliščih, tako da ima vsaka komponenta gozda vsaj tri vozlišča, potem velja ▫$\gamma_{tg}(F) \le 4n/5$▫ in ▫$\gamma_{tg}'(F) \le (4n+2)/5$▫. Kot posledico tega rezultata dobimo zgornji meji za igri na gozdovih, ki so brez izoliranih vozlišč.
    Vir: Preprint series [Elektronski vir]. - ISSN 2232-2094 (Vol. 52, št. 1195, 2014, str. 1-22)
    Vrsta gradiva - e-članek
    Leto - 2014
    Jezik - angleški
    COBISS.SI-ID - 16919641

    Povezava(-e):

    http://www.imfm.si/preprinti/PDF/01195.pdf

Vnos na polico