Domination game played on trees and spanning subgraphs

The domination game, played on a graph GG, was introduced in Brešar et al. (2010) [2]. Vertices are chosen, one at a time, by two players Dominator and Staller. Each chosen vertex must enlarge the set of vertices of GG dominated to that point in the game. Both players use an optimal strategy—Dominator plays so as to end the game as quickly as possible, and Staller plays in such a way that the game lasts as many steps as possible. The game domination number γg(G)γg(G) is the number of vertices chosen when Dominator starts the game and the Staller-start game domination number γg′(G) is the result when Staller starts the game.In this paper these two games are studied when played on trees and spanning subgraphs. A lower bound for the game domination number of a tree in terms of the order and maximum degree is proved and shown to be asymptotically tight. It is shown that for every kk, there is a tree TT with (γg(T),γg′(T))=(k,k+1) and conjectured that there is none with (γg(T),γg′(T))=(k,k−1). A relation between the game domination number of a graph and its spanning subgraphs is considered. It is proved that there exist 3-connected graphs GG having a 2-connected spanning subgraph HH such that the game domination number of HH is arbitrarily smaller than that of GG. Similarly, for any integer ℓ≥1ℓ≥1, there exists a graph GG and a spanning tree TT such that γg(G)−γg(T)≥ℓγg(G)−γg(T)≥ℓ. On the other hand, there exist graphs GG such that the game domination number of any spanning tree of GG is arbitrarily larger than that of GG.