VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Predominating a vertex in the connected domination game
    Bujtás, Csilla ; Iršič, Vesna, 1993- ; Klavžar, Sandi
    Povezana igra dominacije se igra enako kot igra dominacije z dodatno zahtevo, da v vsaki fazi igre vozlišča, ki so se že igrala, tvorijo povezan podgraf. Število potez v igri D (oziroma igri S) na ... grafu ▫$G$▫, ko oba igralca igrata optimalno, je označeno z ▫$\gamma_{\rm cg}(G)$▫ (oziroma ▫$\gamma_{\rm cg}'(G)$)▫. Vzpostavljeno je načelo nadaljevanja povezane igre, ki služi kot nadomestek za klasično načelo nadaljevanja, ki ne velja za povezano igro dominacije. Naj ▫$G|x$▫ označuje graf ▫$G$▫ skupaj z izjavo, da je vozlišče ▫$x$▫ že dominirano. Prvi glavni rezultat trdi, da če je ▫$G$▫ graf z ▫$\gamma_{\rm cg}(G) \geq 3$▫ in ▫$x \in V(G)$▫, potem ▫$\gamma_{\rm cg}(G|x) \leq 2 \gamma_{\rm cg}(G) - 3$▫ in je meja ostra. Drugi glavni izrek pravi, da če je ▫$G$▫ graf z ▫$n(G) \geq 2$▫ in ▫$x \in V(G)$▫, potem je ▫$\gamma_{\rm cg}(G|x) \geq \left \lceil \frac12 \gamma_{\rm cg}(G) \right \rceil$▫ in meja je ostra. Opisani so tudi grafi ▫$G$▫ in njihova vozlišča ▫$x$▫, za katere velja ▫$\gamma_{\rm cg}'(G|x) = \infty$▫.
    Vir: Graphs and combinatorics. - ISSN 0911-0119 (Vol. 38, iss. 3, June 2022, art. 77 (21 str.))
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2022
    Jezik - angleški
    COBISS.SI-ID - 102517507

    Povezava(-e):

    https://link.springer.com/article/10.1007/s00373-022-02478-y
    DOI

vir: Graphs and combinatorics. - ISSN 0911-0119 (Vol. 38, iss. 3, June 2022, art. 77 (21 str.))
loading ...
loading ...
loading ...

Vnos na polico