Akademska digitalna zbirka SLovenije - logo
VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Domination game: extremal families of graphs for 3/5-conjectures
    Brešar, Boštjan ...
    Igralca, Dominator in Zavlačevalka, izmenoma izbirata vozlišča grafa ▫$G$▫, takoda vsako izbrano vozlišče poveča množico do sedaj dominiranih vozlišč. Cilj Dominatorja je končati igro čim hitreje, ... medtem ko je Zavlačevalkin cilj ravno nasprotno. Igralno dominacijsko število ▫$\gamma_g(G)$▫ je skupno število izbranih vozlišč v igri, ko Dominator naredi prvo potezo in oba igralca igrata optimalno. Postavljena je bila domneva [W.B. Kinnersley, D.B. West, R. Zemani, Extremal problems for game domination number, Manuscript, 2012], da velja ▫$\gamma_g(G) \leq \frac{3|V(G)|}{5}$▫ za poljuben graf ▫$G$▫ brez izoliranih vozlišč. V posebnem je domneva odprta tudi, ko je ▫$G$▫ gozd. V tem članku predstavimo konstrukcije, ki nam dajo velike družine dreves, ki dosežejo domnevno mejo ▫$3/5$▫. Leplenje dreves iz nekaterih izmed teh družin napoljuben graf nam da konstrukcijo grafov ▫$G$▫, ki imajo igralno dominacijsko število enako ▫$3|V(G)|/5$▫. Z računalnikom smo poiskali vsa ekstremna drevesa znajveč 20 vozlišči. V posebnem, na 20 vozliščih obstaja natanko deset dreves ▫$T$▫, za katere velja ▫$\gamma_g(T) = 12$▫, in vsa pripadajo skonstruiranim družinam.
    Vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 161, iss. 10-11, 2013, str. 1308-1316)
    Vrsta gradiva - članek, sestavni del
    Leto - 2013
    Jezik - angleški
    COBISS.SI-ID - 16614745

    Povezava(-e):

    http://dx.doi.org/10.1016/j.dam.2013.01.025
    Digitalna knjižnica Univerze v Mariboru – DKUM

vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 161, iss. 10-11, 2013, str. 1308-1316)
loading ...
loading ...
loading ...

Vnos na polico