Domination Game and an Imagination Strategy

Source abstract

The domination game played on a graph G consists of two players, Dominator and Staller, who alternate taking turns choosing a vertex from G such that whenever a vertex is chosen by either player, at least one additional vertex is dominated. Dominator wishes to dominate the graph in as few steps as possible, and Staller wishes to delay the process as much as possible. The game domination number $\gamma_g(G)$ (resp., $\gamma_g'(G)$) is the number of vertices chosen when Dominator (resp., Staller) starts the game. An imagination strategy is developed as a general tool for proving results on the domination game. We show that for any graph G, $\gamma(G)\leq\gamma_g(G)\leq2\gamma(G)-1$, and that all possible values can be realized. It is proved that for any graph G, $\gamma_g(G)-1\leq\gamma'_g(G)\leq\gamma_g(G)+2$, and that most of the possibilities for mutual values of $\gamma_g(G)$ and $\gamma_g'(G)$ can be realized. A connection with Vizing's conjecture is established, and a lower bound on the game domination number of an arbitrary Cartesian product is proved. Several problems and conjectures are also stated.