Domination game on paths and cycles


  • Gašper Košmrlj Abelium d.o.o., Slovenia



Domination game, game domination number, paths, cycles


Domination game is a game on a simple graph played by two players, Dominator and Staller, who are alternating in taking turns. In each turn a player chooses a vertex in such a way that at least one new vertex gets dominated by this move. The game ends when all vertices are dominated, and thus no legal move is possible. As the names of the players suggest, Dominator tries to finish the game as fast as possible, while Staller wants to prolong its end as long as she can. By γg (γgʹ) we denote the total number of moves in the game when Dominator (resp. Staller) starts, and both players play according to their optimal strategies. In a manuscript from 2012, Kinnersley et al. determined γg and γgʹ for paths and cycles, but have not yet published this very important result. In this paper we give an alternative proof for these formulas. Our approach also explicitly describes optimal strategies for both players.