Fast Winning Strategies for the Maker-Breaker Domination Game

The Maker-Breaker domination game is played on a graph G by Dominator and Staller. The players alternatively select a vertex of G that was not yet chosen in the course of the game. Dominator wins if at some point the vertices he has chosen form a dominating set. Staller wins if Dominator cannot form a dominating set. In this paper we introduce the Maker-Breaker domination number γMB(G) of G as the minimum number of moves of Dominator to win the game provided that he has a winning strategy and is the first to play. If Staller plays first, then the corresponding invariant is denoted γ M B ′ ( G ) . Comparing the two invariants it turns out that they behave much differently than the related game domination numbers. The invariant γMB(G) is also compared with the domination number. Using the Erdős-Selfridge Criterion a large class of graphs G is found for which γMB(G) > γ(G) holds. Residual graphs are introduced and used to bound/determine γMB(G) and γ M B ′ ( G ) . Using residual graphs, γMB(T) and γ M B ′ ( T ) are determined for an arbitrary tree. The invariants are also obtained for cycles. A list of open problems and directions for further investigations is given.