Maker-Breaker domination game on trees when Staller wins
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916122729644032 |
|---|---|
| author | Bujtás, Csilla Dokyeesun, Pakanun Klavžar, Sandi |
| author_facet | Bujtás, Csilla Dokyeesun, Pakanun Klavžar, Sandi |
| contents | 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 $γ_{\rm SMB}(G)$ (resp., $γ_{\rm SMB}'(G)$) denotes the minimum number of moves Staller needs to win. For every positive integer $k$, trees $T$ with $γ_{\rm SMB}'(T)=k$ are characterized and a general upper bound on $γ_{\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 $γ_{\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 $γ_{\rm SMB}'(S(n_1,\dots, n_\ell))=\lceil \log_2(n_1+n_2+1)\rceil$. For caterpillars, exact formulas for $γ_{\rm SMB}$ and for $γ_{\rm SMB}'$ are established. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_06530 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Maker-Breaker domination game on trees when Staller wins Bujtás, Csilla Dokyeesun, Pakanun Klavžar, Sandi Combinatorics 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 $γ_{\rm SMB}(G)$ (resp., $γ_{\rm SMB}'(G)$) denotes the minimum number of moves Staller needs to win. For every positive integer $k$, trees $T$ with $γ_{\rm SMB}'(T)=k$ are characterized and a general upper bound on $γ_{\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 $γ_{\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 $γ_{\rm SMB}'(S(n_1,\dots, n_\ell))=\lceil \log_2(n_1+n_2+1)\rceil$. For caterpillars, exact formulas for $γ_{\rm SMB}$ and for $γ_{\rm SMB}'$ are established. |
| title | Maker-Breaker domination game on trees when Staller wins |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2212.06530 |