Domination game played on trees and spanning subgraphs

Bostjan Bresar, Sandi Klavzar, Douglas F. Rall

Published 2012-10-01, updated 2013-03-13Version 2

The domination game is played on a graph G. 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 while Staller plays in such a way that the game lasts as many steps as possible. The game domination number of G is the number of vertices chosen when Dominator starts the game and the Staller-start game domination number of G 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 k, there is a tree T with game domination number k and Staller-start game domination number k+1, and it is conjectured that there is no tree with game domination number k and Staller-start game domination number k-1. A relation between the game domination number of a graph and its spanning subgraphs is considered. It is proved that for any positive integer n, there exists a graph G and its spanning tree T such that the game domination number of G is at least n more than the game domination number of T. Moreover, there exist 3-connected graphs G having a spanning subgraph such that the game domination number of the spanning subgraph is arbitrarily smaller than that of G.