Maker-Breaker domination game on trees when Staller wins
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2023-09-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/10515/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849344686406238208 |
|---|---|
| author | Csilla Bujtás Pakanun Dokyeesun Sandi Klavžar |
| author_facet | Csilla Bujtás Pakanun Dokyeesun Sandi Klavžar |
| author_sort | Csilla Bujtás |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-c0edcc97560e4659881534e13b7f41de |
| institution | Kabale University |
| issn | 1365-8050 |
| language | English |
| publishDate | 2023-09-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-c0edcc97560e4659881534e13b7f41de2025-08-20T03:42:37ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502023-09-01vol. 25:2Graph Theory10.46298/dmtcs.1051510515Maker-Breaker domination game on trees when Staller winsCsilla BujtásPakanun DokyeesunSandi KlavžarIn 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.http://dmtcs.episciences.org/10515/pdfmathematics - combinatorics |
| spellingShingle | Csilla Bujtás Pakanun Dokyeesun Sandi Klavžar Maker-Breaker domination game on trees when Staller wins Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics |
| title | Maker-Breaker domination game on trees when Staller wins |
| title_full | Maker-Breaker domination game on trees when Staller wins |
| title_fullStr | Maker-Breaker domination game on trees when Staller wins |
| title_full_unstemmed | Maker-Breaker domination game on trees when Staller wins |
| title_short | Maker-Breaker domination game on trees when Staller wins |
| title_sort | maker breaker domination game on trees when staller wins |
| topic | mathematics - combinatorics |
| url | http://dmtcs.episciences.org/10515/pdf |
| work_keys_str_mv | AT csillabujtas makerbreakerdominationgameontreeswhenstallerwins AT pakanundokyeesun makerbreakerdominationgameontreeswhenstallerwins AT sandiklavzar makerbreakerdominationgameontreeswhenstallerwins |