DIKUL - logo
(UL)
PDF
  • Maker-Breaker resolving game
    Kang, Cong X. ...
    Množica vozlišč ▫$W$▫ grafa ▫$G$▫ je solventna, če je vsako vozlišče v ▫$G$▫ enolično določeno z vektorjem razdalj do ▫$W$▫. V tem članku vpeljemo solventno igro izdelovalec-lomilec. Igro na grafu ... igrata Izdelovalec in Lomilka, ki izmenično izbirata vozišča grafa, ki še niso bila izbrana. Izdelovalec zmaga, če v nekem trenutku vozlišča, ki jih je izbral, tvorijo solventno množico grafa ▫$G$▫, medtem ko Lomilka zmaga, če Izdelovalec ne more izbrati solventne množice. Rezultat igre označimo z ▫$o(G)$▫, medtem ko ▫$R_{\rm MB}(G)$▫ (oz. ▫$S_{\rm MB}(G)$▫) označuje minimalno število potez Izdelovalca (oz. Lomilke) potrebnih za zmago, ko ima Izdelovalec prvo potezo. Ustrezni invarianti, ko Lomilka začne igro, označimo z ▫$R'_{\rm MB}(G)$▫ in ▫$S'_{\rm MB}(G)$▫. V članku med seboj primerjamo invariante ▫$R_{\rm MB}(G)$▫, ▫$R'_{\rm MB}(G)$▫, ▫$S_{\rm MB}(G)$▫ in ▫$S'_{\rm MB}(G)$▫ ter jih primerjamo z metrično dimenzijo ▫${\rm dim}(G)$▫. Konstruiramo velik razred grafov ▫$G$▫, za katere velja ▫$R_{\rm MB}(G) > {\rm dim}(G)$▫. Opisan je učinek ekvivalenčnih razredov dvojčkov in solventnih množic parov na solventno igro izdelovalec-lomilec. Kot aplikacija je določen ▫$o(G)$▫ kot tudi ▫$R_{\rm MB}(G)$▫ in ▫$R'_{\rm MB}(G)$▫ (ali ▫$S_{\rm MB}(G)$▫ in ▫$S'_{\rm MB}(G)$▫) za različne družine grafov, med drugim za drevesa, polne multipartitne grafe, rešetke in torusne rešetke.
    Vir: Bulletin of the Malaysian Mathematical Sciences Society. - ISSN 0126-6705 (Vol. 44, iss. 4, July 2021, str. 2081-2099)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2021
    Jezik - angleški
    COBISS.SI-ID - 66623491

    Povezava(-e):

    https://link.springer.com/article/10.1007/s40840-020-01044-0
    DOI

Vnos na polico