Maker-Breaker domination number

Abstract

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 ${\gamma }_{\mathrm{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 ${\gamma }_{\mathrm{MB}}^{\prime }(G)$. Comparing the two invariants it turns out that they behave much differently than the related game domination numbers. The invariant ${\gamma }_{\mathrm{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 ${\gamma }_{\mathrm{MB}}(G)>\gamma (G)$ holds. Residual graphs are introduced and used to bound/determine ${\gamma }_{\mathrm{MB}}(G)$ and ${\gamma }_{\mathrm{MB}}^{\prime }(G)$. Using residual graphs, ${\gamma }_{\mathrm{MB}}(T)$ and ${\gamma }_{\mathrm{MB}}^{\prime }(T)$ are determined for an arbitrary tree. The invariants are also obtained for cycles and bounded for union of graphs. A list of open problems and directions for further investigations is given.

20 pages, 5 figures

References in corpus (2)

• Domination game played on trees and spanning subgraphs
• Local resilience and Hamiltonicity Maker-Breaker games in random-regular graphs