Maker-Breaker total domination number

Abstract

The Maker-Breaker total domination number, ${\gamma }_{\mathrm{MBT}}(G)$, of a graph $G$ is introduced as the minimum number of moves of Dominator to win the Maker-Breaker total domination game, provided that he has a winning strategy and is the first to play. The Staller-start Maker-Breaker total domination number, ${\gamma }_{\mathrm{MBT}}^{\prime }(G)$, is defined analogously for the game in which Staller starts. Upper and lower bounds on ${\gamma }_{\mathrm{MBT}}(G)$ and on ${\gamma }_{\mathrm{MBT}}^{\prime }(G)$ are provided and demonstrated to be sharp. It is proved that for any pair of integers $(k,\ell )$ with $2\le k\le \ell$, (i) there exists a connected graph $G$ with ${\gamma }_{\mathrm{MB}}(G)=k$ and ${\gamma }_{\mathrm{MBT}}(G)=\ell$, (ii) there exists a connected graph $G^{\prime }$ with ${\gamma }_{\mathrm{MB}}^{\prime }(G^{\prime })=k$ and ${\gamma }_{\mathrm{MBT}}^{\prime }(G^{\prime })=\ell$, and (iii) there there exists a connected graph $G^{\prime \prime }$ with ${\gamma }_{\mathrm{MBT}}(G^{\prime \prime })=k$ and ${\gamma }_{\mathrm{MBT}}^{\prime }(G^{\prime \prime })=\ell$. Here, ${\gamma }_{\mathrm{MB}}$ and ${\gamma }_{\mathrm{MB}}^{\prime }$ are corresponding invariants for the Maker-Breaker domination game.