| Naslov: | Maker-Breaker domination game on trees when Staller wins |
|---|
| Avtorji: | ID Bujtás, Csilla (Avtor)
ID Dokyeesun, Pakanun (Avtor)
ID Klavžar, Sandi (Avtor) |
|---|
| Datoteke: |  PDF - Predstavitvena datoteka, prenos (255,58 KB)
MD5: D9ABDC296CA33CAD76EB9FE4F838BFE7
 URL - Izvorni URL, za dostop obiščite https://dmtcs.episciences.org/12202
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | In the Maker-Breaker domination game played on a graph $G$, Dominator's goal is to select a dominating set and Staller's goal is to claim a closed neighborhood of some vertex. We study the cases when Staller can win the game. If Dominator (resp., Staller) starts the game, then $\gamma_{\rm SMB}(G)$ (resp., $\gamma_{\rm SMB}'(G)$) denotes the minimum number of moves Staller needs to win. For every positive integer $k$, trees $T$ with $\gamma_{\rm SMB}'(T)=k$ are characterized and a general upper bound on $\gamma_{\rm SMB}'$ is proved. Let $S = S(n_1,\dots, n_\ell)$ be the subdivided star obtained from the star with $\ell$ edges by subdividing its edges $n_1-1, \ldots, n_\ell-1$ times, respectively. Then $\gamma_{\rm SMB}'(S)$ is determined in all the cases except when $\ell\ge 4$ and each $n_i$ is even. The simplest formula is obtained when there are at least two odd $n_i$s. If ▫$n_1$▫ and $n_2$ are the two smallest such numbers, then $\gamma_{\rm SMB}'(S(n_1,\dots, n_\ell))=\lceil \log_2(n_1+n_2+1)\rceil$▫. For caterpillars, exact formulas for $\gamma_{\rm SMB}$ and for $\gamma_{\rm SMB}'$ are established. |
|---|
| Ključne besede: | domination game, Maker-Breaker game, Maker-Breaker domination game, hypergraphs, trees, subdivided stars, caterpillars |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.01.2023 |
|---|
| Leto izida: | 2023 |
|---|
| Št. strani: | 21 str. |
|---|
| Številčenje: | Vol. 25, no. 2, [article no.] 12 |
|---|
| PID: | 20.500.12556/DiRROS-18631  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 1365-8050 |
|---|
| DOI: | 10.46298/dmtcs.10515 |
|---|
| COBISS.SI-ID: | 164065283 |
|---|
| Opomba: |
|
|---|
| Datum objave v DiRROS: | 08.04.2024 |
|---|
| Število ogledov: | 632 |
|---|
| Število prenosov: | 254 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
