The domination game is a two-player game played on a graph. The players have two roles, Dominator and Staller. Dominator wants to finish the game as soon as possible, while Staller tries to postpone the end of the game for as long as possible. The two players alternate turns and each turn they pick a vertex, and color the vertex itself and its neighbors. The players should always color at least one previously uncolored vertex. When all vertices are colored the game is finished. Calculating bounds on the total number of moves under optimal play for all graphs with n vertices is a hard open problem. In this research, the domination game on a specific family of graphs is analyzed, the king graphs. These are modeled after how kings move on a chessboard and provide an interesting graph with a lot of structure, but nontrivial optimal winning strategies.
For small boards, we found the optimal move counts with computer search for up to 9 x 9 boards. For general n, lower and upper bounds on the number of moves were found. For an n x n king graph, the number of moves under optimal play, gamma_g(G_n), satisfies
2/10n^2 - O(n) <= gamma_g(G_n) <= 2/9 n^2 + O(n).