VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Maker-Breaker domination game on trees when Staller wins [Elektronski vir]
    Bujtás, Csilla ; Dokyeesun, Pakanun ; Klavžar, Sandi
    V dominacijski igri izdelovalec-lomilec na grafu ▫$G$▫ je Dominatorjev cilj izbrati dominantno množico, Zavlačevalkin cilj pa zasesti zaprto okolico nekega vozlišča. Preučujemo primere, ko zmaga ... Zavlačevalka. Če Dominator (oziroma Zavlačevalka) začne igro, potem ▫$\gamma_{\rm SMB}(G)$▫ (oziroma ▫$\gamma'_{\rm SMB}(G)$▫) označuje najmanjše število potez, ki jih Zavlačevalka potrebuje za zmago. Za vsako pozitivno celo število ▫$k$▫ so opisana drevesa ▫$T$▫ z ▫$\gamma'_{\rm SMB}(T)=k$▫ in dokazana je splošna zgornja meja za ▫$\gamma_{\rm SMB}'$▫. Naj bo ▫$S = S(n_1,\dots, n_\ell)$▫ subdividirana zvezda, ki jo dobimo iz zvezde z ▫$\ell$▫ povezavami tako, da njene povezave subdividiramo ▫$n_1-1, \ldots, n_\ell-1$▫ krat. Potem je ▫$\gamma_{\rm SMB}'(S)$▫ določena v vseh primerih, razen kadar je ▫$\ell\ge 4$▫ in je vsak ▫$n_i$▫ sod. Najpreprostejšo formulo dobimo, kadar sta vsaj dva liha ▫$n_i$▫. Če sta ▫$n_1$▫ in ▫$n_2$▫ dve najmanjši taki števili, potem je ▫$\gamma_{\rm SMB}'(S(n_1,\dots, n_\ell))=\lceil \log_2(n_1+n_2+1)\rceil$▫. Za gosenice sta določeni natančni formuli za ▫$\gamma_{\rm SMB}$▫ in ▫$\gamma_{\rm SMB}'$▫.
    Vir: Discrete mathematics & theoretical computer science [Elektronski vir]. - ISSN 1365-8050 (Vol. 25, no. 2, [article no.] 12, 2023, 21 str.)
    Vrsta gradiva - e-članek ; neleposlovje za odrasle
    Leto - 2023
    Jezik - angleški
    COBISS.SI-ID - 164065283

    Povezava(-e):

    https://dmtcs.episciences.org/12202
    Repozitorij Univerze v Ljubljani – RUL
    DiRROS - Digitalni repozitorij raziskovalnih organizacij Slovenije
    DOI

Vnos na polico