VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
PDF
  • The enclaveless competition game
    Henning, Michael A. ; Rall, Douglas F.
    Če je ▫$S$▫ podmnožica vozlišč grafa ▫$G$▫, potem vozlišču ▫$v \in S$▫ pravimo enklava množice ▫$S$▫, če je vozlišče ▫$v$▫, pa tudi vsi njegovi sosedje, v množici ▫$S$▫, pri čemer je sosed vozlišča v ... tisto vozlišče, ki je sosedno vozlišču ▫$v$▫. Množica ▫$S$▫ je brezenklavna, če nima enklav. Brezenklavno število ▫$\Psi(G)$▫ grafa ▫$G$▫ je kardinalnost največje brezenklavne množice v ▫$G$▫. Kot je prvi opazil Slater leta 1997: če je ▫$G$▫ graf na ▫$n$▫ vozliščih, potem je ▫$\gamma(G) + \Psi(G) = n$▫, kjer je ▫$\gamma(G)$▫ dobro raziskano dominacijsko število grafa ▫$G$▫. V članku nadaljujemo raziskavo tekmovalne brezenklavne igre, ki sta jo leta 2001 vpeljala Philips in Slater in je definirana takole: dva igralca izmenično konstruirata maksimalno brezenklavno množico ▫$S$▫, pri čemer en igralec, povečevalec, poizkuša maksimalizirati ▫$|S|$▫, drug igralec, pomanjševalec, pa poizkuša minimalizirati ▫$|S|$▫. Vrednost tekmovalne brezenklavne igre ▫$\Psi_g^+(G)$▫ grafa ▫$G$▫ je število vozlišč, dobljenih v primeru, da povečevalec začne igro in da oba igralca igrata optimalno. Poleg drugih problemov raziskujemo domnevo, da če je ▫$G$▫ graf brez izoliranih vozlišč reda ▫$n$▫, potem je ▫$\Psi_g^+(G) \geq \frac{1}{2} n$▫. To domnevo dokažemo za regularne grafe in za brezkrempljaste grafe.
    Vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 20, no. 1, 2021, str. 129-142)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2021
    Jezik - angleški
    COBISS.SI-ID - 91621123

    Povezava(-e):

    https://amc-journal.eu/index.php/amc/article/download/2227/1680
    Digitalna knjižnica Slovenije - dLib.si
    DOI

Vnos na polico