Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.01259 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914526156292096 |
|---|---|
| author | Sampaio, Rudini Filho, Edileudo Maciel M. Paz, Jefter G. Maciel Brito, João Marcos |
| author_facet | Sampaio, Rudini Filho, Edileudo Maciel M. Paz, Jefter G. Maciel Brito, João Marcos |
| contents | The Domination game is an impartial game on graphs, introduced in 2010, and proved PSPACE-complete in the normal variant in 2026. In this game, Alice and Bob alternately select playable vertices, where a vertex is playable if it dominates at least one vertex not dominated by the vertices selected before in the game. The game ends when the selected vertices form a dominating set. In the normal variant, the player unable to move loses. In contrast to the impartial game, the partizan game has the vertices already colored with $A$, $B$, or $C$, in such a way that Alice (resp. Bob) can only select vertices colored with $A$ (resp. $B$) or $C$. The partizan game was proved PSPACE-hard in 2026. In this paper, we determine the winner of the Normal Partizan Domination game in graphs whose components are complete split graphs, including star forests, for any initial coloring of its vertices. We also obtain partial results for complete bipartite graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_01259 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Normal Domination Partizan Game in Stars Sampaio, Rudini Filho, Edileudo Maciel M. Paz, Jefter G. Maciel Brito, João Marcos Combinatorics Discrete Mathematics The Domination game is an impartial game on graphs, introduced in 2010, and proved PSPACE-complete in the normal variant in 2026. In this game, Alice and Bob alternately select playable vertices, where a vertex is playable if it dominates at least one vertex not dominated by the vertices selected before in the game. The game ends when the selected vertices form a dominating set. In the normal variant, the player unable to move loses. In contrast to the impartial game, the partizan game has the vertices already colored with $A$, $B$, or $C$, in such a way that Alice (resp. Bob) can only select vertices colored with $A$ (resp. $B$) or $C$. The partizan game was proved PSPACE-hard in 2026. In this paper, we determine the winner of the Normal Partizan Domination game in graphs whose components are complete split graphs, including star forests, for any initial coloring of its vertices. We also obtain partial results for complete bipartite graphs. |
| title | The Normal Domination Partizan Game in Stars |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2605.01259 |