Biased domination games
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929445981388800 |
|---|---|
| author | Bagdas, Ali Deniz Clemens, Dennis Hamann, Fabian Mogge, Yannick |
| author_facet | Bagdas, Ali Deniz Clemens, Dennis Hamann, Fabian Mogge, Yannick |
| contents | We consider a biased version of Maker-Breaker domination games, which were recently introduced by Gledel, Ir{š}i{č}, and Klav{ž}ar. Two players, Dominator and Staller, alternatingly claim vertices of a graph $G$ where Dominator is allowed to claim up to $b$ vertices in every round and she wins if and only if she occupies all vertices of a dominating set of $G$. For this game, we prove a full characterization of all trees on which Dominator has a winning strategy. For the number of rounds which Dominator needs to win, we give exact results when played on powers of paths or cycles, and for all trees we provide bounds which are optimal up to a constant factor not depending on $b$. Furthermore, we discuss general minimum degree conditions and study how many vertices can still be dominated by Dominator even when Staller has a winning strategy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_00529 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Biased domination games Bagdas, Ali Deniz Clemens, Dennis Hamann, Fabian Mogge, Yannick Combinatorics 05C57, 05C05, 05C69 We consider a biased version of Maker-Breaker domination games, which were recently introduced by Gledel, Ir{š}i{č}, and Klav{ž}ar. Two players, Dominator and Staller, alternatingly claim vertices of a graph $G$ where Dominator is allowed to claim up to $b$ vertices in every round and she wins if and only if she occupies all vertices of a dominating set of $G$. For this game, we prove a full characterization of all trees on which Dominator has a winning strategy. For the number of rounds which Dominator needs to win, we give exact results when played on powers of paths or cycles, and for all trees we provide bounds which are optimal up to a constant factor not depending on $b$. Furthermore, we discuss general minimum degree conditions and study how many vertices can still be dominated by Dominator even when Staller has a winning strategy. |
| title | Biased domination games |
| topic | Combinatorics 05C57, 05C05, 05C69 |
| url | https://arxiv.org/abs/2408.00529 |