Domination game played on trees and spanning subgraphs

The domination game, played on a graph G , 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 G 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 ) 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. s 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 k , there is a tree T 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 G having a 2-connected spanning subgraph H such that the game domination number of H is arbitrarily smaller than that of G . Similarly, for any integer ℓ ≥ 1 , there exists a graph G and a spanning tree T such that γ g ( G ) − γ g ( T ) ≥ ℓ . On the other hand, there exist graphs G such that the game domination number of any spanning tree of G is arbitrarily larger than that of G .