DIKUL - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • Domination game and an imagination strategy
    Brešar, Boštjan ; Klavžar, Sandi ; Rall, Douglas F.
    Igro dominacije, ki se odvija na grafu ▫$G$▫, igrata dva igralca, Dominator in Zavlačevalec, ki se izmenjujeta v potezah, ki so takšne izbire vozlišča iz ▫$G$▫, da je po izbiri vozlišča s strani ... katerega koli igralca vsaj eno dodatno vozlišče dominirano. Dominator želi dominirati graf v čim manj potezah, Zavlačevalec pa želi, da ta postopek traja čim dlje. Igralno dominantno število grafa ▫$\gamma_g(G)$▫ (▫$\gamma_g'(G)$▫) je število izbranih vozlišč v igri, ki jo začne Dominator ( Zavlačevalec). V članku razvijemo imaginacijsko strategijo kot splošno orodje za dokazovanje rezultatov o igri dominacije. Dokažemo, da za vsak graf ▫$G$▫ velja ▫$\gamma(G)\le \gamma_g(G)\le 2\gamma(G)-1$▫ in da so lahko vse možne vrednosti realizirane. Dokazano je, da za vsak graf ▫$G$▫ velja ▫$\gamma_g(G)-1\le \gamma_g'(G)\le \gamma_g(G)+2$▫ in da se večina možnosti za skupne vrednosti ▫$\gamma_g(G)$▫ in ▫$\gamma_g'(G)$▫ lahko realizira. Ugotovljena je povezava z Vizingovo domnevo in dokazana spodnja meja za igralno dominantno število poljubnega kartezičnega produkta. Zastavljenih je tudi več problemov in domnev.
    Vir: SIAM journal on discrete mathematics. - ISSN 0895-4801 (Vol. 24, no. 3, 2010, str. 979-991)
    Vrsta gradiva - članek, sestavni del
    Leto - 2010
    Jezik - angleški
    COBISS.SI-ID - 15648089

    Povezava(-e):

    http://dx.doi.org/10.1137/100786800

vir: SIAM journal on discrete mathematics. - ISSN 0895-4801 (Vol. 24, no. 3, 2010, str. 979-991)

loading ...
loading ...
loading ...

Vnos na polico