Maker-Breaker Sabotage Game

Abstract

The Maker-Breaker sabotage game is played on a graph $G$ by Runner and Blocker. They play in turns, Runner first moves along a not yet traversed edge from her current position, afterwards Blocker removes one edge. The goal of Runner is to visit as many vertices of $G$ as possible, Blocker's goal is opposite. Assuming that both players use optimal strategies, the number of vertices visited by Runner determines an invariant called the sabotage number $\mathrm{sab}(G)$ of $G$. A formula for the sabotage number of an arbitrary tree is proved which can be evaluated in polynomial time. For a unicyclic graph $G$ it is proved that $\mathrm{sab}(G)\in \{{\mathrm{sab}}^{-}(G),{\mathrm{sab}}^{-}(G)+1\}$, where ${\mathrm{sab}}^{-}(G)$ is the lower sabotage number of $G$. The sabotage number of a bridgeless subcubic graph is sharply bounded from the above by the maximum girth. The sabotage number is also bounded for complete bipartite graphs and generalized Sierpiński graphs, and determined exactly in some special cases.