DIKUL - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • Domination game played on trees and spanning subgraphs [Elektronski vir]
    Brešar, Boštjan ; Klavžar, Sandi ; Rall, Douglas F.
    Igra dominacije na grafu ▫$G$▫ je bila vpeljana v [B. Brešar, S. Klavžar, D. F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979-991]. Dva igralca, Dominator in ... Zavlačevalec, drug za drugim izbirata po eno vozlišče grafa. Vsako izbrano vozlišče mora povečati množico vozlišč, ki so bila dominirana do tega trenutka igre. Oba igralca izbirata optimalno strategijo, pri čemer Dominator želi igro končati v najmanjšem možnem številu korakov, Zavlačevalec pa v največjem možnem številu korakov. Igralno dominacijsko število ▫$\gamma_g(G)$▫ je število izbranih vozlišč v igri, kjer je Dominator prvi izbral vozlišče. Ustrezno invarianto, ko igro začne Zavlačevalec, označimo z ▫$\gamma_g'(G)$▫. V članku sta obe igri proučevani na drevesih in vpetih podgrafih. Dokazana je spodnja meja za igralno dominacijsko število drevesa, ki je funkcija njegovega reda in maksimalne stopnje. Pokazano je, da je meja asimptotično optimalna. Dokazano je, da za vsak ▫$k$▫ obstaja drevo ▫$T$▫ z ▫$(\gamma_g(T),\gamma_g'(T)) = (k,k+1)$▫ in postavljena je domneva, da ne obstaja drevo z ▫$(\gamma_g(T),\gamma_g'(T)) = (k,k-1)$▫. Obravnavana je povezava med igralnim dominacijskim številom grafa in njegovimi vpetimi podgrafi. Dokazano je, da za vsako naravno število ▫$\ell \geq 1$▫ obstaja graf ▫$G$▫ z vpetim drevesom ▫$T$▫, tako da velja ▫$\gamma_g(G)-\gamma_g(T)\ge \ell$▫. Nadalje obstajajo 3-povezani grafi ▫$G$▫, ki imajo vpeta drevesa z igralnim dominacijskim številom poljubno manjšim od ▫$G$▫.
    Vir: Preprint series [Elektronski vir]. - ISSN 2232-2094 (Vol. 49, št. 1162, 2011, str. 1-14)
    Vrsta gradiva - e-članek
    Leto - 2011
    Jezik - angleški
    COBISS.SI-ID - 16027993

    Povezava(-e):

    http://www.imfm.si/preprinti/PDF/01162.pdf
    Digitalna knjižnica Univerze v Mariboru – DKUM

Vnos na polico