# Fast winning strategies for Staller in the Maker-Breaker domination game

Csilla Bujtás Pakanun Dokyeesun Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The Maker-Breaker domination game is played on a graph $G$ by two players,
called Dominator and Staller, who alternately choose a vertex that has not
been played so far. Dominator wins the game if his moves form a dominating
set. Staller wins if she plays all vertices from a closed neighborhood of a
vertex $v\in V(G)$. Dominator’s fast winning strategies were studied earlier.
In this work, we concentrate on the cases when Staller has a winning strategy
in the game. We introduce the invariant $\gamma^{\prime}_{\rm SMB}(G)$ (resp.,
$\gamma_{\rm SMB}(G)$) which is the smallest integer $k$ such that, under any
strategy of Dominator, Staller can win the game by playing at most $k$
vertices, if Staller (resp., Dominator) plays first on the graph $G$.

We prove some basic properties of $\gamma_{\rm SMB}(G)$ and
$\gamma^{\prime}_{\rm SMB}(G)$ and study the parameters’ changes under some
operators as taking the disjoint union of graphs or deleting a cut vertex. We
show that the inequality $\delta(G)+1\leq\gamma^{\prime}_{\rm
SMB}(G)\leq\gamma_{\rm SMB}(G)$ always holds and that for every three integers
$r,s,t$ with $2\leq r\leq s\leq t$, there exists a graph $G$ such that
$\delta(G)+1=r$, $\gamma^{\prime}_{\rm SMB}(G)=s$, and $\gamma_{\rm
SMB}(G)=t$. We prove exact formulas for $\gamma^{\prime}_{\rm SMB}(G)$ where
$G$ is a path, or it is a tadpole graph which is obtained from the disjoint
union of a cycle and a path by adding one edge between them.

Faculty of Mathematics and Physics

University of Ljubljana, Slovenia

Keywords: domination game; Maker-Breaker game; winning number; Maker-Breaker
domination game; closed neighborhood hypergraph

##  1 Introduction

A general frame for studying Maker-Breaker games was introduced by Erdős and
Selfridge [13] nearly $50$ years ago. Since then, several variants have been
defined and studied extensively [18]. In this work, we are interested in the
Maker-Breaker domination game [12]. In particular, we focus on the cases when
Breaker (i.e., Staller) wins the game and consider Breaker’s fast winning
strategies. Along this way, we translate the problem to the Maker-Breaker game
played on the closed neighborhood hypergraph of a graph. We establish sharp
lower and upper bounds on the corresponding graph invariants and determine the
exact values for paths and tadpole graphs.

###  1.1 Standard definitions

Throughout the paper, we denote by $V(G)$ and $E(G)$, respectively, the vertex
and edge set of a graph $G$. For a vertex $v\in V(G)$, the _open neighborhood_
$N_{G}(v)$ contains the neighbors of $v$ and the _closed neighborhood_ of $v$
is defined as $N_{G}[v]=N_{G}(v)\cup\\{v\\}$. Then, $\deg_{G}(v)=|N_{G}(v)|$.
For a set $S\subseteq V(G)$ we use the analogous notation
$N_{G}(S)=\bigcup_{v\in S}N_{G}(v)$ and $N_{G}[S]=\bigcup_{v\in S}N_{G}[v]$.
If the graph is clear from the context, we omit the index and simply write
$N(v)$, $N[v]$, $N(S)$, and $N[S]$. A vertex $v$ is a leaf if $\deg_{G}(v)=1$,
and the neighbor of a leaf is a support vertex. A support vertex is said to be
a strong support vertex if it is adjacent to at least two leaves. Otherwise,
we call it a weak support vertex.

A vertex dominates itself and its neighbors. A set $D\subseteq V(G)$ is a
_dominating set_ in $G$ if $N[D]=V(G)$. The minimum cardinality of such a set
is the _domination number_ of $G$ and denoted by $\gamma(G)$. A dominating set
is _minimal_ if it does not contain any dominating set as a proper subset.

A hypergraph ${\cal H}$ is a set system over the underlying vertex set
$V({\cal H})$. Equivalently, the set $E({\cal H})$ of its (hyper)edges is a
subset of $2^{V({\cal H})}$. In general, we assume that each $e\in E({\cal
H})$ contains at least one vertex, but sometimes we do not exclude the case of
$e=\emptyset$. For the latter situation, we will always mention this
possibility directly. A hypergraph is _$k$ -uniform_ if $|e|=k$ for every
$e\in E({\cal H})$ and it is _simple_ if $e\not\subseteq f$ holds for every
two different edges. Note that a simple graph is just a simple $2$-uniform
hypergraph. We say that ${\cal H}_{1}$ is a _subhypergraph_ of ${\cal H}_{2}$,
if $E({\cal H}_{1})\subseteq E({\cal H}_{2})$.

A vertex set $T\subseteq V({\cal H})$ is a _transversal_ (or vertex cover) in
a hypergraph ${\cal H}$ if it meets every edge of ${\cal H}$. Assuming
$\emptyset\notin E({\cal H})$, the minimum cardinality of a transversal is the
_transversal number_ $\tau({\cal H})$ of the hypergraph. A _minimal
transversal_ of ${\cal H}$ is a transversal that does not contain any other
transversal as a proper subset. Following Berge’s notation, we denote by
$Tr({\cal H})$ the hypergraph on the vertex set $V({\cal H})$ that contains
all minimal transversals of ${\cal H}$ as hyperedges. We cite a related result
of Berge.

######  Proposition 1.1 (Corollary 1, pp. 44 [2])

Let ${\cal H}_{1}$ and ${\cal H}_{2}$ be two simple hypergraphs on the same
vertex set. Then, $Tr({\cal H}_{1})={\cal H}_{2}$ if and only if $Tr({\cal
H}_{2})={\cal H}_{1}$.

We also introduce an operator, named _simplification_ , on hypergraphs that
transforms ${\cal H}$ into $\widehat{{\cal H}}$ by sequentially removing,
while it is possible, an edge $e\in E(H)$ if it contains another edge as a
subset. It is clear by definition that $\widehat{{\cal H}}$ is a simple
hypergraph and that $T$ is a (minimal) transversal in ${\cal H}$ if and only
if it is a (minimal) transversal in $\widehat{{\cal H}}$.

Given a graph $G$, we define two hypergraphs on the same vertex set $V(G)$.
Let ${\cal D}_{G}$ be the hypergraph that contains all the minimal dominating
sets of $G$ as hyperedges and let ${\cal H}_{G}$ be the hypergraph with edge
set $E({\cal H}_{G})=\\{N_{G}[v]:v\in V(G)\\}$. According to the standard
terminology, we say that ${\cal H}_{G}$ is the _closed neighborhood
hypergraph_ of $G$. By definition, $D\subseteq V(G)$ is a minimal dominating
set in $G$ if and only if it is a minimal transversal in the closed
neighborhood hypergraph ${\cal H}_{G}$. Observe that ${\cal D}_{G}$ is a
simple hypergraph for every $G$. These observations together with Proposition
1.1 imply the following statement.

###### Proposition 1.2

It holds for every graph $G$ that $Tr({\cal H}_{G})={\cal D}_{G}$ and
$Tr({\cal D}_{G})=\widehat{{\cal H}_{G}}$.

###  1.2 Winning number in a Maker-Breaker game

The Maker-Breaker game is played by two persons, namely Maker and Breaker, on
a hypergraph ${\cal H}$. The vertex set $V({\cal H})$ is called the _board_ of
the game while the edges of ${\cal H}$ are interpreted as winning sets. The
two players alternately choose (i.e., play) an unplayed vertex from the board.
We say that a player _claims_ the set $S\subseteq V({\cal H})$ if he (or she)
plays all vertices of $S$. It is a _Maker-start game_ (resp., _Breaker-start
game_) if Maker (resp., Breaker) is the first to play. _Maker wins_ the game
if he claims a winning set while _Breaker wins_ if she can prevent Maker from
doing this. The latter equivalently means that Breaker plays at least one
vertex from each winning set, that is, she claims a minimal transversal of
${\cal H}$. We may conclude the following.

###### Observation 1.3

A Maker-Breaker game on ${\cal H}$ with a player A as Maker and a player B as
Breaker is the same as the Maker-Breaker game on $Tr({\cal H})$ where the
roles of A and B are switched.

In the last decades, several variants of the Maker-Breaker game were specified
and intensively studied. These include the connectivity game [14, 17], the
hamiltonicity game [3, 24, 25], the Maker-Breaker resolving [22], domination
[12, 16] and total domination [15] games. For other versions and references
see [18].

Fast winning strategies were also studied for some types of Maker-Breaker
games [10, 11, 12, 15, 16, 22]. We introduce here four hypergraph invariants
to measure how fast a player can win in a (general) Maker-Breaker game. Assume
first that a Maker-Breaker game is played on ${\cal H}$ and Maker can win the
game when he is the first player. We say that Maker wins in his $i^{\rm th}$
move if he claims a winning set (i.e., an edge of ${\cal H}$) with this move.
We suppose that Maker’s goal is to win the game as soon as possible and that
Breaker’s goal is just the opposite. The _winning number of Maker_ , denoted
by ${\rm w}_{M}^{M}({\cal H})$, is the minimum number of his moves he needs to
win the game if both players play optimally. If Maker has no winning strategy
as a first player, we set ${\rm w}_{M}^{M}({\cal H})=\infty$. When it is a
Breaker-start game, ${\rm w}_{M}^{B}({\cal H})$ is defined similarly.

Now, consider the problem from Breaker’s point of view. We say that the game
is over and Breaker wins in her $i^{\rm th}$ move if she claims a minimal
transversal of ${\cal H}$ with this move. Clearly, this situation makes it
impossible for Maker to claim a winning set even if the game would be
continued. Analogously to the previous case, we assume that Breaker’s goal is
to win the game by playing as few vertices as possible, while Maker’s goal is
the opposite. Then, if Maker starts the game and Breaker has a winning
strategy, the _winning number of Breaker_ , ${\rm w}_{B}^{M}({\cal H})$, is
the minimum number of her moves needed to win the game if both players play
optimally. Further, ${\rm w}_{B}^{M}({\cal H})=\infty$, if Breaker cannot win
the game. For the game when Breaker is the a first player, ${\rm
w}_{B}^{B}({\cal H})$ is defined analogously. Concerning the notation ${\rm
w}_{X}^{Y}$ in general, for every pair $(X,Y)$ with $X,Y\in\\{M,B\\}$ the
superscript $Y$ denotes the player who starts the game while the subscript $X$
indicates the player whose fast winning strategies are considered.

If ${\rm w}_{X}^{Y}({\cal H})$ equals $\infty$ (for $X,Y\in\\{M,B\\}$) by
definition, we consider it as an infinite cardinality number (e.g.,
$\aleph_{0}$) and refer to it in calculations or relations accordingly. For
instance, for every hypergraph ${\cal H}$ and $X\in\\{M,B\\}$, ${\rm
w}_{M}^{X}({\cal H})+{\rm w}_{B}^{X}({\cal H})=\infty$ always holds, while
${\rm w}_{M}^{X}({\cal H})<{\rm w}_{B}^{X}({\cal H})$ means that Maker has a
winning strategy in the game if $X$ plays first. By Observation 1.3, ${\rm
w}_{M}^{M}({\cal H})={\rm w}_{B}^{B}(Tr({\cal H}))$ and ${\rm w}_{M}^{B}({\cal
H})={\rm w}_{B}^{M}(Tr({\cal H}))$.

###  1.3 Maker-Breaker domination game

The Maker-Breaker domination game (_MBD game_ for short) was recently
introduced in [12] and further studied in [16]. The MBD game on a graph $G$ is
a Maker-Breaker game played on ${\cal D}_{G}$. Following the terminology
introduced for the earlier versions of the domination game [4, 5, 6, 7, 8, 19,
20, 23], Maker and Breaker are respectively called Dominator and Staller in an
MBD game. An MBD game is called _D-game_ if Dominator starts the game and it
is an _S-game_ if Staller starts. By Observation 1.3 and Proposition 1.2, a
Maker-Breaker domination game on a graph $G$ can also be considered as a
Maker-Breaker game on the closed neighborhood hypergraph ${\cal H}_{G}$ (or on
its simplification $\widehat{{\cal H}_{G}}$) where Staller is the Maker and
Dominator is the Breaker.

Now suppose that Dominator has a winning strategy on $G$ in the D-game. As it
was introduced in [16], the minimum number of moves of Dominator to win the
game is the Maker-Breaker domination number (_MBD-number_) $\gamma_{\rm
MB}(G)$. If Dominator does not have a winning strategy, we set $\gamma_{\rm
MB}(G)=\infty$. In terms of the winning number defined for the general case,
$\gamma_{\rm MB}(G)={\rm w}_{M}^{M}({\cal D}_{G})$. Similarly, for the S-game,
$\gamma_{\rm MB}^{\prime}(G)={\rm w}_{M}^{B}({\cal D}_{G})$.

In this paper, as proposed in [16], we consider the problem from Staller’s
point of view. Suppose that Staller has a strategy to win the (MBD) D-game on
a graph $G$. Then, Staller wins in her $i^{\rm th}$ move if she claims a
minimal transversal of ${\cal D}_{G}$ with this move. It equivalently means
that she can claim a closed neighborhood $N_{G}[v]$ of a vertex $v$. The
_Staller-Maker-Breaker domination number_ (_SMBD-number_) $\gamma_{\rm
SMB}(G)$ of $G$ is the minimum number of Staller’s moves she needs to win the
D-game if both players play optimally. If Staller has no winning strategy in
the D-game, we set $\gamma_{\rm SMB}(G)=\infty$. This definition gives
$\gamma_{\rm SMB}(G)={\rm w}_{B}^{M}({\cal D}_{G})={\rm w}_{M}^{B}({\cal
H}_{G})$. For the S-game, the invariant $\gamma_{\rm SMB}^{\prime}(G)$ is
defined analogously and we have $\gamma_{\rm SMB}^{\prime}(G)={\rm
w}_{B}^{B}({\cal D}_{G})={\rm w}_{M}^{M}({\cal H}_{G})$.

By definition, a Maker-Breaker game is a finite game and there is always a
winner. Therefore, for each graph $G$ either both $\gamma_{\rm MB}(G)<\infty$
and $\gamma_{\rm SMB}(G)=\infty$ hold, or $\gamma_{\rm MB}(G)=\infty$ and
$\gamma_{\rm SMB}(G)<\infty$. The analogous statement is true for the
invariants related to the S-game. Further, as it was shown in [17, Proposition
2.1.6, pp. 15] for the Maker-Breaker game in general, if Staller (Dominator)
can win as the second player, then she (he) can win as the first player. Then,
$\gamma_{\rm SMB}(G)<\infty$ implies $\gamma_{\rm SMB}^{\prime}(G)<\infty$.

In this work, we concentrate on the cases where Staller wins in at least one
of the D- and S-game that is if $\gamma_{\rm SMB}^{\prime}(G)<\infty$.
Typically, we will consider the Maker-Breaker game on the closed neighborhood
hypergraph ${\cal H}_{G}$.

#### Structure of the paper.

In Section 2.1 we study the behavior of the winning numbers under some changes
in the hypergraph such as taking disjoint union, deleting or shrinking edges.
Then, in Section 2.2, we state similar results for the SMBD-numbers of a graph
and prove the inequality $\delta(G)+1\leq\gamma_{\rm
SMB}^{\prime}(G)\leq\gamma_{\rm SMB}(G)$ and the No-Skip Lemma. Section 3 is
devoted to a construction which shows that for every three integers satisfying
$2\leq r\leq s\leq t$ there exists a graph $G$ with $\delta(G)+1=r$,
$\gamma_{\rm SMB}(G)=s$, and $\gamma_{\rm SMB}^{\prime}(G)=t$. In Section 4,
we consider the changes of SMBD-numbers if a leaf and its support vertex is
removed from a graph. Applying the previous propositions, it is proved in
Section 5 that $\gamma_{\rm SMB}^{\prime}(P_{n})=\lfloor\log_{2}n\rfloor+1$
holds for every path of odd order. The SMBD-numbers of tadpole graphs (that
can be obtained from a cycle and a path by adding an edge between a vertex of
the cycle and an endvertex of the path) are determined in Section 6. Some
additional observations and conjectures are provided in Section 7.

##  2 Basic properties

In this section we state several basic properties of the Maker-Breaker games
in general, on the MBD games, and their hypergraph representation.

###  2.1 Basics for Maker-Breaker games

We introduce two operators on hypergraphs that help us modeling Maker’s and
Breaker’s moves. Let ${\cal H}$ be a hypergraph and $X\subseteq V({\cal H})$.
The hypergraph ${\cal H}-X$ is obtained from ${\cal H}$ by deleting the
vertices contained in $X$ and also deleting all incident edges. Formally,

$V({\cal H}-X)=V({\cal H})\setminus X\qquad\mbox{and}\qquad E({\cal
H}-X)=\\{e:e\in E({\cal H})\enskip{\rm and}\enskip e\cap X=\emptyset\\}.$

The other operator is named _shrinking_ and the resulted hypergraph is denoted
by ${\cal H}\mid X$. It means that the vertices in $X$ are deleted from ${\cal
H}$ but we keep the remaining parts of the incident edges. That is,

$V({\cal H}\mid X)=V({\cal H})\setminus X\qquad\mbox{and}\qquad E({\cal H}\mid
X)=\\{e\setminus X:e\in E({\cal H})\\}.$

Note that shrinking may transform a simple hypergraph into a non-simple one.
In particular, it may create some empty edges. If $X$ contains only one vertex
$v$, we may write ${\cal H}-v$ and ${\cal H}\mid v$ instead of ${\cal
H}-\\{v\\}$ and ${\cal H}\mid\\{v\\}$, respectively.

In a Maker-Breaker game, the winning sets can be modified after each move of
the players as follows.

###### Proposition 2.1

Suppose that a Maker-Breaker game is played on a hypergraph ${\cal H}$ and
$v\in V({\cal H})$.

  * $(i)$

If Breaker is the first player and she plays $v$, the continuation of the game
corresponds to a Maker-start game on ${\cal H}-v$. In particular, if $v$ is an
optimal first move of Breaker, then ${\rm w}_{M}^{B}({\cal H})={\rm
w}_{M}^{M}({\cal H}-v)$.

  * $(ii)$

If Maker is the first player and he plays $v$, the continuation of the game
corresponds to a Breaker-start game on ${\cal H}\mid v$. In particular, if $v$
is an optimal first move of Maker, then ${\rm w}_{M}^{M}({\cal H})={\rm
w}_{M}^{B}({\cal H}\mid v)+1$. Further, Maker wins the game with this move $v$
if and only if ${\cal H}\mid v$ contains an empty hyperedge but ${\cal H}$
does not.

Proof. $(i)$ After Breaker plays $v$, this vertex cannot be played anymore,
and none of the incident edges can be claimed by Maker. As the other winning
sets remain untouched, Maker may imagine that he starts a Maker-Breaker game
on ${\cal H}-v$ with his next move. Concerning the equality ${\rm
w}_{M}^{B}({\cal H})={\rm w}_{M}^{M}({\cal H}-v)$, recall that only Maker’s
moves are counted for ${\rm w}_{M}^{B}({\cal H})$.

$(ii)$ If Maker plays $v$ on ${\cal H}$, this vertex cannot be played in the
continuation. Further, if $v$ belongs to a winning set $e\in E({\cal H})$
then, in the continuation, it is enough to claim $e\setminus\\{v\\}$ for Maker
to win the game. Thus, the players may imagine that the continuation is a
Breaker-start game on ${\cal H}\mid v$. It is also clear that Maker claims a
winning set with the move $v$ if and only if $\\{v\\}\in E({\cal H})$ that is
equivalent to $\emptyset\in E({\cal H}\mid v)$. $\square$

Next we show that adding some new winning sets or shrinking some of the
winning sets is never disadvantageous for Maker.

###### Proposition 2.2

Let ${\cal H}_{1}$ and ${\cal H}_{2}$ be two hypergraphs on the same vertex
set.

  * $(i)$

If $E({\cal H}_{1})\subseteq E({\cal H}_{2})$, then ${\rm w}_{M}^{M}({\cal
H}_{1})\geq{\rm w}_{M}^{M}({\cal H}_{2})$ and ${\rm w}_{M}^{B}({\cal
H}_{1})\geq{\rm w}_{M}^{B}({\cal H}_{2})$ holds.

  * $(ii)$

Suppose that for each $e\in E({\cal H}_{1})$ there exists an edge
$e^{\prime}\in E({\cal H}_{2})$ such that $e^{\prime}\subseteq e$. Then, ${\rm
w}_{M}^{M}({\cal H}_{1})\geq{\rm w}_{M}^{M}({\cal H}_{2})$ and ${\rm
w}_{M}^{B}({\cal H}_{1})\geq{\rm w}_{M}^{B}({\cal H}_{2})$ holds.

Proof. As $(i)$ can be considered as a special case of $(ii)$, it is enough to
prove the second statement. If ${\rm w}_{M}^{M}({\cal H}_{1})=\infty$ or ${\rm
w}_{M}^{B}({\cal H}_{1})=\infty$, the corresponding inequality clearly holds.
Otherwise, suppose that Maker plays on ${\cal H}_{2}$ (as the first player)
following a strategy that is optimal for ${\cal H}_{1}$ while Breaker plays
optimally on ${\cal H}_{2}$. Maker’s strategy ensures that, under any strategy
of Breaker, he claims a winning set from $E({\cal H}_{1})$ in at most ${\rm
w}_{M}^{M}({\cal H}_{1})$ moves. Let this winning set be $e\in E({\cal
H}_{1})$ in the current game. Since there is a winning set $e^{\prime}$ in
${\cal H}_{2}$ so that $e^{\prime}\subseteq e$, Maker wins on ${\cal H}_{2}$
either with this move or earlier. This proves ${\rm w}_{M}^{M}({\cal
H}_{1})\geq{\rm w}_{M}^{M}({\cal H}_{2})$. The argument is similar if Breaker
starts the game. $\square$

Propositions 2.1 and 2.2 together imply that, during a Maker-Breaker game,
skipping a move or playing an isolated vertex (i.e., a vertex of degree $0$ in
${\cal H}$) is never advantageous for Maker. The same is true for Breaker
concerning her moves.

###### Proposition 2.3

Let ${\cal H}$ be a disconnected hypergraph that consists of the components
${\cal H}_{1},\dots,{\cal H}_{\ell}$ such that ${\rm w}_{M}^{M}({\cal
H}_{1})\leq\dots\leq{\rm w}_{M}^{M}({\cal H}_{\ell})$. Then, the following
holds:

${\rm w}_{M}^{M}({\cal H})={\rm w}_{M}^{M}({\cal H}_{1})\qquad{\rm
and}\qquad{\rm w}_{M}^{M}({\cal H}_{1})\leq{\rm w}_{M}^{B}({\cal H})\leq{\rm
w}_{M}^{M}({\cal H}_{2}).$

Proof. Since $E({\cal H}_{1})\subseteq E({\cal H})$, Proposition 2.2 (i)
implies ${\rm w}_{M}^{M}({\cal H})\leq{\rm w}_{M}^{M}({\cal H}_{1})$. On the
other hand, Breaker may reply to each move of Maker by playing an optimal move
in the same component. This strategy ensures the game on ${\cal H}$ not being
finished before Maker’s ${\rm w}_{M}^{M}({\cal H}_{1})^{\rm th}$ move. We
infer of ${\rm w}_{M}^{M}({\cal H})={\rm w}_{M}^{M}({\cal H}_{1})$.

By Proposition 2.1 (i) and Proposition 2.2 (i), ${\rm w}_{M}^{M}({\cal
H})\leq{\rm w}_{M}^{B}({\cal H})$ always holds. Thus, ${\rm w}_{M}^{M}({\cal
H})={\rm w}_{M}^{M}({\cal H}_{1})$ implies ${\rm w}_{M}^{M}({\cal
H}_{1})\leq{\rm w}_{M}^{B}({\cal H})$. For the upper bound, if Breaker starts
the game on ${\cal H}$ by selecting a vertex $v$, consider the following
strategy of Maker. If $v\in V({\cal H}_{1})$, Maker plays according to an
optimal strategy on ${\cal H}_{2}$ from the next move on. This ensures that
the game finishes in his ${\rm w}_{M}^{M}({\cal H}_{2})^{\rm th}$ move or
earlier. If $v\notin V({\cal H}_{1})$ then, from the next move, Maker plays
according to an optimal strategy on ${\cal H}_{1}$ and ensures that the game
finishes in his ${\rm w}_{M}^{M}({\cal H}_{1})^{\rm th}$ move or earlier. As
${\rm w}_{M}^{M}({\cal H}_{1})\leq{\rm w}_{M}^{M}({\cal H}_{2})$, we may
conclude ${\rm w}_{M}^{B}({\cal H})\leq{\rm w}_{M}^{M}({\cal H}_{2})$.
$\square$

###  2.2 Basics for Maker-Breaker domination games

Recall that an MBD game on a graph $G$ corresponds to a Maker-Breaker game on
the closed neighborhood hypergraph ${\cal H}_{G}$ with $\gamma_{\rm
SMB}^{\prime}(G)={\rm w}_{M}^{M}({\cal H}_{G})$ and $\gamma_{\rm SMB}(G)={\rm
w}_{M}^{B}({\cal H}_{G})$. When we consider an MBD game in which Staller has
already played the vertices from $S$ and Dominator has played the vertices
from $D$, we will often refer to the hypergraph of current winning sets. By
Proposition 2.1, this hypergraph is $({\cal H}_{G}\mid S)-D$. To prove lower
bounds on $\gamma_{\rm SMB}(G)$ or $\gamma_{\rm SMB}^{\prime}(G)$ we often
modify the hypergraph ${\cal H}$ of current winning sets by adding new winning
sets or replacing an $e\in E({\cal H})$ with an $e^{\prime}\subseteq e$. By
Proposition 2.2, it makes easier for Staller to win. In the other case, when
we want to prove an upper bound on $\gamma_{\rm SMB}(G)$ or $\gamma_{\rm
SMB}^{\prime}(G)$, we can modify ${\cal H}$ by deleting some winning sets or
replacing an $e\in E({\cal H})$ with an $e^{\prime}\supseteq e$.

If $G$ consists of the components $G_{1},\dots,G_{\ell}$, then ${\cal H}_{G}$
consists of the components ${\cal H}_{G_{1}},\dots\cal H_{G_{\ell}}$. This
fact and Proposition 2.3 readily imply the following statement.

###### Proposition 2.4

If a disconnected graph $G$ consists of the components $G_{1},\dots,G_{\ell}$
and $\gamma_{\rm SMB}^{\prime}(G_{1})\leq\dots\leq\gamma_{\rm
SMB}^{\prime}(G_{\ell})$, then the following statements hold:

  * $(i)$

$\gamma_{\rm SMB}^{\prime}(G)=\gamma_{\rm SMB}^{\prime}(G_{1})$;

  * $(ii)$

$\gamma_{\rm SMB}^{\prime}(G_{1})\leq\gamma_{\rm SMB}(G)\leq\gamma_{\rm
SMB}^{\prime}(G_{2})$.

###### Proposition 2.5

Let $v$ be a cut vertex in a connected graph $G$. If $G_{1},\dots,G_{\ell}$
are the components of $G-v$ indexed so that $\gamma_{\rm
SMB}^{\prime}(G_{1})\leq\dots\leq\gamma_{\rm SMB}^{\prime}(G_{\ell})$, then

$\gamma_{\rm SMB}^{\prime}(G)\leq\gamma_{\rm SMB}^{\prime}(G_{2})+1.$

Proof. If $\gamma_{\rm SMB}^{\prime}(G_{2})=\infty$, the inequality is clearly
valid. Otherwise, consider the strategy of Staller when she plays $v$ as the
first move in the game on $G$. By Proposition 2.1, the continuation of the
game is the same as it would be on ${\cal H}_{G}\mid v$. As $v$ is a cut
vertex in $G$, the hypergraph ${\cal H}_{G}\mid v$ corresponds to the disjoint
union of the closed neighborhood hypergraphs of $G_{1},\dots,G_{\ell}$
supplemented with an extra hyperedge $e=N_{G}(v)$. Deleting $e$ from ${\cal
H}_{G}\mid v$, we obtain the hypergraph ${\cal H}^{\prime}$. By Proposition
2.2, we have ${\rm w}_{M}^{B}({\cal H}_{G}\mid v)\leq{\rm w}_{M}^{B}({\cal
H}^{\prime})$. Observe that ${\cal H}^{\prime}$ contains $\ell$ components,
namely ${\cal H}_{G_{1}},\dots,{\cal H}_{G_{\ell}}$. By Proposition 2.4, ${\rm
w}_{M}^{M}({\cal H}^{\prime})\leq\gamma_{\rm SMB}^{\prime}(G_{2})$ and,
therefore, Staller can ensure that she wins after playing at most
$1+\gamma_{\rm SMB}^{\prime}(G_{2})$ vertices (together with her first move).
$\square$

As a further consequence of Propositions 2.1 and 2.2, we get the following
statement which is analogous to the No-Skip Lemma proved in [16] for the MBD
games when Dominator’s fast winning strategies and the parameters $\gamma_{\rm
MB}(G)$ and $\gamma_{\rm MB}^{\prime}(G)$ were studied.

######  Lemma 2.6 (No-Skip Lemma)

In an optimal strategy of Staller to achieve $\gamma_{\rm SMB}(G)$ or
$\gamma_{\rm SMB}^{\prime}(G)$ it is never an advantage for her to skip a
move. Moreover, if Dominator skips a move it can never disadvantage Staller.

We close this section with a simple but important relation between the minimum
degree $\delta(G)$ and the invariants $\gamma_{\rm SMB}(G)$, $\gamma_{\rm
SMB}^{\prime}(G)$.

###### Proposition 2.7

If $G$ is a graph with minimum degree $\delta(G)$, then

$\delta(G)+1\leq\gamma_{\rm SMB}^{\prime}(G)\leq\gamma_{\rm SMB}(G).$ (1)

Proof. Clearly, $\delta(G)+1\leq\gamma_{\rm SMB}^{\prime}(G)$ as Staller can
win the game only by claiming a closed neighborhood a vertex. To show
$\gamma_{\rm SMB}^{\prime}(G)\leq\gamma_{\rm SMB}(G)$, we consider the D-game
as an S-game in which Staller skips the first move. By Lemma 2.6, $\gamma_{\rm
SMB}^{\prime}(G)\leq\gamma_{\rm SMB}(G)$. $\square$

It is clear that the presence of an isolated vertex implies $\gamma_{\rm
SMB}^{\prime}(G)=1$ and we may easily construct a graph $G_{t}$ for each
$t\geq 1$ such that $\delta(G)=0$, $\gamma_{\rm SMB}^{\prime}(G)=1$ and
$\gamma_{\rm SMB}(G)=t$. In Section 3, we will show that for every triple of
integers $(r,s,t)$ with $2\leq r\leq s\leq t$ there exists a graph $G$
satisfying $\delta(G)+1=r$, $\gamma_{\rm SMB}(G)=s$, and $\gamma_{\rm
SMB}^{\prime}(G)=t$.

##  3 A realization theorem for $\delta$, $\gamma_{\rm SMB}^{\prime}$, and
$\gamma_{\rm SMB}$

We start with the definition of two families of graphs. Let $F_{1}$ be
isomorphic to $P_{3}$ and $X_{1}\subseteq V(F_{1})$ contain the two leaves and
let $z_{1}$ denote the support (central) vertex. For $k\geq 2$, we construct
$F_{k}$ by using two copies of $F_{k-1}$, namely $F_{k-1}^{1}$ and
$F_{k-1}^{2}$, and adding a new vertex $z_{k}$ which is adjacent to every
vertex in $X_{k-1}^{1}\cup X_{k-1}^{2}$. Let us define $X_{k}=X_{k-1}^{1}\cup
X_{k-1}^{2}$ and $Y_{k}=V(F_{k})\setminus(X_{k}\cup\\{z_{k}\\})$. It is clear
by the recursive definition that $|X_{k}|=2^{k}$ and each vertex from $X_{k}$
is of degree $k$. Moreover, $Y_{k}$ contains $2^{k-i}$ vertices of degree
$2^{i}$ for all $i\in[k-1]$ and, therefore, $|Y_{k}|=2^{k}-2$.

We define $F^{\prime}_{k}$ by modifying $F_{k}$ as follows. For $i\in[2]$, let
$F^{\prime}_{i}\cong F_{i}$. If $k\geq 3$, $F^{\prime}_{k}$ is obtained from
$F_{k}$ by adding a complete graph of order $k-1$. We denote by $Y^{+}_{k}$
the set of these $k-1$ new vertices and supplement the graph with a join
between $Y^{+}_{k}$ and $Y_{k}$. Observe that $\deg_{F_{k}^{\prime}}(v)>k$
holds for all $v\in Y_{k}\cup Y_{k}^{+}$ and therefore,
$\delta(F_{k}^{\prime})=k$.

$z_{1}$$F_{1}\cong F^{\prime}_{1}$$z_{2}$$F_{2}\cong
F^{\prime}_{2}$$Y_{2}$$X_{2}$$X_{1}$

$X_{3}$$Y_{3}$$Y^{+}_{3}$$z_{3}$$F^{\prime}_{3}$

Figure 1: Graphs $F^{\prime}_{1}\cong F_{1}$, $F^{\prime}_{2}\cong F_{2}$, and
$F^{\prime}_{3}$. In $F_{3}^{\prime}$ every vertex in $Y^{+}_{3}$ is adjacent
to every vertex in $Y_{3}$.

###### Lemma 3.1

For every positive integer $k$, $\gamma_{\rm
SMB}^{\prime}(F^{\prime}_{k})=k+1$ and $\gamma_{\rm
SMB}(F^{\prime}_{k})=\infty$.

Proof. Let $k$ be a positive integer. Since $\delta(F_{k}^{\prime})=k$,
Proposition 2.7 shows that $\gamma_{\rm SMB}^{\prime}(F^{\prime}_{k})\geq
k+1$. To prove $\gamma_{\rm SMB}^{\prime}(F^{\prime}_{k})\leq k+1$, we
describe an appropriate strategy for Staller in the S-game. Staller plays
$z_{k}$ in her first move. According to the construction,
$F_{k}^{\prime}-z_{k}$ contains two disjoint copies of $F_{k-1}$. Thus, after
Dominator’s first move, there remains a subgraph $F_{k-1}^{i}$ such that none
of its vertices are played and Staller may claim its center $z_{k-1}^{i}$ in
her second move. Then, $F_{k-1}^{i}-z_{k-1}^{i}$ contains two copies of
$F_{k-2}$ and at least one of them remains unplayed after the next move of
Dominator. From this unplayed $F_{k-2}^{j}$ subgraph, Staller plays the center
$z_{k-2}^{j}$. Continuing this way, in her $\ell^{\rm th}$ move, $\ell\in[k]$,
Staller plays the center of a copy of $F_{k-\ell+1}$. As the described
strategy ensures, after Staller’s $k^{\rm th}$ move, there remain two
vertices, say $x_{1}$ and $x_{2}$, such that all vertices from
$N_{F_{k}^{\prime}}(x_{1})=N_{F_{k}^{\prime}}(x_{2})$ have been already
claimed by Staller. After Dominator’s $k^{\rm th}$ move, Staller may play one
of these vertices, say $x_{1}$, and win the game by claiming
$N_{F_{k}^{\prime}}[x_{1}]$. This strategy shows that $\gamma_{\rm
SMB}^{\prime}(F^{\prime}_{k})\leq k+1$ and then $\gamma_{\rm
SMB}^{\prime}(F^{\prime}_{k})=k+1$ follows..

We next show that $\gamma_{\rm SMB}(F^{\prime}_{k})=\infty$ for every positive
integer $k$. Dominator wins the D-game in $F_{1}^{\prime}$ with his first move
by playing $z_{1}$. In $F_{2}^{\prime}$, Dominator first plays $z_{2}$ and
then he can claim one (unplayed) vertex from each component of
$F_{2}^{\prime}-z_{2}$ as his second and third move. This way Dominator can
always claim a dominating set in $F_{2}^{\prime}$. If $k\geq 3$, Dominator may
start the game by playing $z_{k}$. We remark that there remains at least one
unplayed vertex in $Y^{+}_{k}$ after the first move of Staller. If Dominator
responds by playing such a vertex, he claims a dominating set with this move.
We therefore conclude $\gamma_{\rm SMB}(F^{\prime}_{k})=\infty$. $\square$

By Proposition 2.7, $\delta(G)+1\leq\gamma_{\rm
SMB}^{\prime}(G)\leq\gamma_{\rm SMB}(G)$ holds for every graph $G$. The
following realization theorem implies the sharpness of this inequality (1),
and also that the differences $\gamma_{\rm SMB}(G)-\gamma_{\rm
SMB}^{\prime}(G)$ and $\gamma_{\rm SMB}^{\prime}(G)-\delta(G)$ can be
arbitrarily large.

###### Theorem 3.2

For every three integers $r,s,t$ with $2\leq r\leq s\leq t$, there exists a
graph $G$ such that $\delta(G)+1=r$, $\gamma_{\rm SMB}^{\prime}(G)=s$, and
$\gamma_{\rm SMB}(G)=t$.

Proof. Let $r,s,t$ be integers such that $2\leq r\leq s\leq t$ and let
$G_{r,s,t}$ be the disjoint union of a copy of $K_{r}$, a copy of
$F^{\prime}_{s-1}$, and a copy of $F^{\prime}_{t-1}$. We show that
$\delta(G_{r,s,t})+1=r$, $\gamma_{\rm SMB}^{\prime}(G_{r,s,t})=s$, and
$\gamma_{\rm SMB}(G_{r,s,t})=t$ hold.

Notice first that $\delta(K_{r})=r-1$, $\delta(F^{\prime}_{s-1})=s-1$, and
$\delta(F^{\prime}_{t-1})=t-1$. Thus, $\delta(G_{r,s,t})+1=r$. As $r\geq 2$ is
supposed, Dominator wins in $K_{r}$ both in a D-game and S-game that is,
$\gamma_{\rm SMB}(K_{r})=\gamma_{\rm SMB}^{\prime}(K_{r})=\infty$. By Lemma
3.1, $\gamma_{\rm SMB}^{\prime}(F^{\prime}_{s-1})=s$, $\gamma_{\rm
SMB}^{\prime}(F^{\prime}_{t-1})=t$, and $\gamma_{\rm
SMB}(F^{\prime}_{s-1})=\gamma_{\rm SMB}(F^{\prime}_{t-1})=\infty$. Proposition
2.4 (i) immediately implies $\gamma_{\rm SMB}^{\prime}(G)=s$.

Now consider a D-game played on $G_{r,s,t}$. By Proposition 2.4 (ii),
$\gamma_{\rm SMB}(G_{r,s,t})\leq t$ holds. To prove the other direction, we
present a strategy for Dominator which guarantees that Staller needs to play
at least $t$ vertices to win. Dominator first plays $z_{s-1}$ in the component
$F^{\prime}_{s-1}$. Then, if Staller plays a vertex from a component, in the
next turn Dominator replies with an optimal move in the same component. This
ensures that Staller cannot win by claiming a closed neighborhood of a vertex
from $V(K_{r})\cup V(F^{\prime}_{s-1})$. As $\delta(F^{\prime}_{t-1})=t-1$, it
needs at least $t$ moves to claim a closed neighborhood of a vertex from
$F^{\prime}_{t-1}$. It follows that $\gamma_{\rm SMB}(G_{r,s,t})\geq t$ and we
infer $\gamma_{\rm SMB}(G_{r,s,t})=t$ $\square$

The disconnected graph $G_{r,s,t}$ in the above proof can be replaced with a
connected graph that still satisfies the required properties. Indeed, fix a
vertex $v\in V(K_{r})$ and add the edges $vz_{s-1}$ and $vz_{t-1}$ to
$G_{r,s,t}$. As $r\geq 2$, the obtained graph $G^{\prime}_{r,s,t}$ is of
minimum degree $r-1$, and it can be shown that both $\gamma_{\rm
SMB}^{\prime}(G^{\prime}_{r,s,t})=s$ and $\gamma_{\rm
SMB}(G^{\prime}_{r,s,t})=t$ remain true.

We note, related to Theorem 3.2, that the statement remains true if the cases
$t=\infty$ and $s=t=\infty$ are allowed. Indeed, deleting the component
$F^{\prime}_{t-1}$ from $G_{r,s,t}$, we obtain a graph with $\delta+1=r$,
$\gamma_{\rm SMB}^{\prime}=s$ and $\gamma_{\rm SMB}=\infty$, while the
deletion of both $F^{\prime}_{s-1}$ and $F^{\prime}_{t-1}$ leaves $K_{r}$ with
$\delta(K_{r})+1=r$ and $\gamma_{\rm SMB}^{\prime}(K_{r})=\gamma_{\rm
SMB}(K_{r})=\infty$.

##  4 Deleting a leaf and a support vertex

The deletion of a strong support vertex and all the adjacent leaves from a
graph $G$ might increase $\gamma_{\rm SMB}^{\prime}(G)$ and $\gamma_{\rm
SMB}(G)$ drastically. In fact, the difference can be arbitrarily large. In
this section we consider the possible changes of the SMBD-numbers when a weak
support vertex and its leaf are removed from a graph.

###### Proposition 4.1

Let $G^{\prime}$ be a graph obtained from $G$ by removing a weak support
vertex and the adjacent leaf. Then, the following inequalities hold:

$\gamma_{\rm SMB}^{\prime}(G)-1\leq\gamma_{\rm
SMB}^{\prime}(G^{\prime})\leq\gamma_{\rm SMB}^{\prime}(G)\qquad{\rm
and}\qquad\gamma_{\rm SMB}(G^{\prime})\leq\gamma_{\rm SMB}(G).$

Proof. Let $u$ be a weak support vertex in $G$ that is adjacent to the leaf
$v$. Then $u$ is a cut vertex in $G$ and $G-u$ is isomorphic to the disjoint
union of $G^{\prime}=G-\\{u,v\\}$ and the isolated vertex $v$. By Proposition
2.5, $\gamma_{\rm SMB}^{\prime}(G)-1\leq\gamma_{\rm
SMB}^{\prime}(G^{\prime})$.

To prove the inequalities $\gamma_{\rm
SMB}^{\prime}(G^{\prime})\leq\gamma_{\rm SMB}^{\prime}(G)$ and $\gamma_{\rm
SMB}(G^{\prime})\leq\gamma_{\rm SMB}(G)$, we use the imagination strategy. Let
Game 1 be an S-game on $G^{\prime}$ where Dominator plays optimally, and let
Game 2 be an S-game on $G$ in which Staller applies an optimal strategy.
Whenever Dominator plays a vertex in Game 1, he copies this move to Game 2.
There Staller replies optimally on $G$, say by playing $s_{i}$, and copies
this move to Game 1 if it is possible. In particular, whenever $s_{i}\in
V(G)\setminus\\{u,v\\}$, Staller can copy the move to Game 1. Observe that if
a winning set in Game 2 contains $v$, it also contains $u$. We may therefore
assume that Staller never plays $v$ while $u$ is also available. If $s_{i}=u$,
then Staller will not play any vertex in Game 1. To continue Game 2, Staller
imagines that Dominator replies by playing $v$ in $G$. Then, if Game 2 is not
yet over, Staller selects an optimal move $s_{i+1}$ in Game 2 and copies it to
Game 1. From this moment, the process continues by simply copying the players’
optimal moves to the other game.

For $i\in[2]$, let $t_{i}$ be the number of Staller’s moves until she wins in
Game $i$ and set $t_{i}=\infty$ if she does not win. Observe that
$N_{G^{\prime}}[x]\subseteq N_{G}[x]$ holds for every vertex $x\in
V(G)\setminus\\{u,v\\}$ and, by the described strategy, Staller cannot win in
$G$ by claiming the entire $N_{G}[u]$ or $N_{G}[v]$. Thus, when Game 2 ends by
the move $s_{t_{2}}$ and it is copied to Game 1, Staller has already claimed a
closed neighborhood in Game 1. We may therefore conclude that $t_{1}\leq
t_{2}$. Suppose first that Staller starts in both Game 1 and Game 2. Since
Dominator plays optimally in Game 1 but Staller might not, we infer
$\gamma_{\rm SMB}^{\prime}(G^{\prime})\leq t_{1}$. Similarly, as Dominator
might not follow an optimal strategy in Game 2, but Staller plays optimally,
we have $t_{2}\leq\gamma_{\rm SMB}^{\prime}(G)$. This proves $\gamma_{\rm
SMB}^{\prime}(G^{\prime})\leq\gamma_{\rm SMB}^{\prime}(G)$. If Dominator
starts in both Game 1 and Game 2, then the same argumentation yields
$\gamma_{\rm SMB}(G^{\prime})\leq\gamma_{\rm SMB}(G)$. $\square$

It is not hard to see that $\gamma_{\rm SMB}(G)-1\leq\gamma_{\rm
SMB}(G^{\prime})$ is not always true for $G$ and $G^{\prime}$ under the
conditions of Proposition 4.1. As an example, we may consider a graph $G$ such
that a weak support vertex $u$ is adjacent to all vertices. In this graph
Dominator may win the D-game with his first move $d_{1}=u$ that implies
$\gamma_{\rm SMB}(G)=\infty$ even if $\gamma_{\rm SMB}(G^{\prime})$ is finite.
However we can prove that $\gamma_{\rm SMB}(G)-1\leq\gamma_{\rm
SMB}(G^{\prime})$ holds under stronger conditions. Note that the removal of a
weak support vertex of degree $2$ and its leaf, had a central role when
Dominator’s fast winning strategies were studied in [16].

###### Proposition 4.2

Let $G$ be a graph with a weak support vertex of degree $2$ and $G^{\prime}$ a
graph obtained from $G$ by removing this weak support vertex and the adjacent
leaf. Then, $\gamma_{\rm SMB}(G)-1\leq\gamma_{\rm SMB}(G^{\prime})$ holds.

Proof. Let $u$ be a weak support vertex in $G$ adjacent to the leaf $v$ and to
the non-leaf vertex $u^{\prime}$. We set $G^{\prime}=G-\\{u,v\\}$ and note
that the closed neighborhoods of vertices in
$V(G)\setminus\\{u,u^{\prime},v\\}$ are the same in $G$ as in $G^{\prime}$. We
prove $\gamma_{\rm SMB}(G)-1\leq\gamma_{\rm SMB}(G^{\prime})$ by using the
imagination strategy and comparing the winning sets in the two games after a
vertex from $\\{u,v,u^{\prime}\\}$ was played. Let Game 1 be a D-game on $G$
where Dominator plays optimally, and Game 2 be a D-game on $G^{\prime}$ where
Staller plays optimally. If neither of $u$, $u^{\prime}$ and $v$ has been
played until a moment in the game, then the moves of the players are simply
copied to the another game. That is, whenever Dominator plays a vertex $d_{i}$
in Game 1, he copies this move to Game 2. There Staller replies optimally on
$G^{\prime}$, say by playing $s_{i}$, and copies this move to Game 1. Under
the given conditions, it is always possible. If a vertex from
$\\{u,v,u^{\prime}\\}$ is played, the corresponding move(s) in the other game
will be specified in Case 1 and 2. For $i\in[2]$, let $t_{i}$ be the number of
Staller’s moves until she wins in Game $i$ and set $t_{i}=\infty$ if she does
not win. We prove $t_{1}\leq t_{2}+1$ by considering three cases.

#### Case 1.

If Dominator plays first a vertex $d_{i}$ from $\\{u,v,u^{\prime}\\}$, this
move belongs to Game 1. We may suppose that Dominator’s corresponding move in
Game 2 is $u^{\prime}$. After these moves, each remaining winning set of
Staller in Game 2 is also a winning set in Game 1. By Proposition 2.2 (i),
this proves $t_{1}\leq t_{2}$.

#### Case 2.

If Staller plays first a vertex $s_{i}$ from $\\{u,v,u^{\prime}\\}$, then
$s_{i}=u^{\prime}$ as this move belongs to Game 2. Note that Case 1 excludes
Case 2 in a game and, therefore, $u$, $u^{\prime}$ and $v$ all are unplayed in
Game 1. We may set $s_{i}=u$ in Game 1. Dominator, who plays optimally there,
has to reply by claiming $v$ as otherwise Staller could win in her next move
by playing $v$. These two moves $u$ and $v$ are not copied to Game 2. Instead,
we set $s_{i+1}=u^{\prime}$ in Game 1 and observe that the winning sets in
Game 1 and Game 2 are the same, while the number of moves of Staller in Game 1
is one more than the number of her moves in Game 2. We may infer
$t_{1}=t_{2}+1$. Remark that this argumentation is also true if Staller
finishes Game 2 with the move $s_{t_{2}}=u^{\prime}$.

#### Case 3.

If neither of $u$, $u^{\prime}$ and $v$ is played during the games, then the
moves are just copied from one game to the other. Further, under this
condition, Staller cannot win by claiming the entire
$N_{G^{\prime}}[u^{\prime}]$, $N_{G}[u^{\prime}]$, $N_{G}[u]$, or $N_{G}[v]$.
For the remaining vertices, we have $N_{G}[x]=N_{G^{\prime}}[x]$ and thus, the
two games end together. This shows $t_{1}=t_{2}$.

We may therefore conclude that $t_{1}\leq t_{2}+1$. Our argumentation is also
valid for the cases when Staller does not win. For this situation, we suppose
that every vertex is played in $G$ and $G^{\prime}$ but no winning set is
claimed by Staller.

Since Dominator plays optimally all along Game 1, we infer $\gamma_{\rm
SMB}(G)\leq t_{1}$. Similarly, as Staller follows an optimal strategy in Game
2, we have $t_{2}\leq\gamma_{\rm SMB}(G^{\prime})$. Together with $t_{1}\leq
t_{2}+1$ we conclude $\gamma_{\rm SMB}(G)\leq\gamma_{\rm SMB}(G^{\prime})+1$.
$\square$

##  5 Paths

The “pairing strategy” of Maker [18] ensures that he can win in the Maker-
Breaker game if an approriate set of vertex pairs can be defined. Its
immediate consequence for the MBD game shows that Dominator has a winning
strategy in both the D-game and S-game if the graph admits a perfect matching.
Here we state the lemma in a more general form.

###### Lemma 5.1

Consider an MBD game on $G$ and let $X$ and $Y$ be the set of vertices played
by Dominator and Staller, respectively, until a moment during the game. If
there exists a matching $M$ in $G-(X\cup Y)$ such that $V(G)\setminus
V(M)\subseteq N_{G}[X]$, then Dominator has a strategy to win the continuation
of the game, no matter who plays the next vertex.

Proof. By the conditions of the lemma,

$(X\cup Y)\subseteq(V(G)\setminus V(M))\subseteq N_{G}[X]$

that is all vertices from $X\cup Y$ are dominated by the first $|X|$ moves of
Dominator. In the continuation Dominator can win the game by applying the
following strategy. If Staller plays a vertex $v$ such that $uv\in E(M)$ and
$u$ has not been played yet, then Dominator plays $u$ in his next turn.
Otherwise, Dominator plays an arbitrary unplayed vertex. As $V(M)$ does not
contain any vertices from $Y$, this startegy makes sure that Dominator plays
at least one vertex from each edge of the matching (unless the game finishes
earlier as the entire $V(M)$ is dominated by Dominator’s moves). We conclude
that Dominator’s moves dominate every vertex from $V(G)=V(M)\cup(V(G)\setminus
V(M))$ and hence, he wins the game. $\square$

As it was shown in [12], Dominator can win the MBD game on all paths and
cycles if he is the first player. Moreover, Dominator also wins the S-game if
it is played on a cycle or a path of an even order. On the other hand, if $n$
is odd, $\gamma_{\rm SMB}^{\prime}(P_{n})<\infty$.

By Proposition 4.1, $\gamma_{\rm SMB}^{\prime}(P_{n+2})\leq\gamma_{\rm
SMB}^{\prime}(P_{n})+1$. Starting with $\gamma_{\rm SMB}^{\prime}(P_{1})=1$
and $\gamma_{\rm SMB}^{\prime}(P_{3})=2$, this yields $\gamma_{\rm
SMB}^{\prime}(P_{2k+1})\leq k+1$. For paths of even order the corresponding
invariant satisfies $\gamma_{\rm MB}^{\prime}(P_{2k})=k$ (see [16]). These
facts might suggest that $\gamma_{\rm SMB}^{\prime}(P_{2k+1})$ is equal to or
not far from $k+1$. However, as we will show, the value of $\gamma_{\rm
SMB}^{\prime}(P_{2k+1})$ is significantly different from $k+1$. The exact
formula is established in the following theorem. If $n\geq 3$ and $n$ is odd,
we may also cite the statement of the theorem in the form of $\gamma_{\rm
SMB}^{\prime}(P_{n})=\lceil\log_{2}n\rceil$.

###### Theorem 5.2

If $n$ is an odd positive integer, then

$\displaystyle\gamma_{\rm
SMB}^{\prime}(P_{n})=\left\lfloor\log_{2}n\right\rfloor+1.$ (2)

Moreover, Staller has an optimal strategy in the S-game on $P_{n}$ such that
she wins on the closed neighborhood of a vertex $v$ that is at an even
distance from the ends of the path.

Proof. First we observe that $\gamma_{\rm SMB}^{\prime}(P_{1})=1$ and
$\gamma_{\rm SMB}^{\prime}(P_{3})=2$ and thus, the formula is valid for $n=1$
and $n=3$. Then we proceed by induction on $n$. Suppose that $n\geq 5$ and (2)
is true for every odd integer which is smaller than $n$. We first prove
$\gamma_{\rm SMB}^{\prime}(P_{n})\leq\left\lfloor\log_{2}n\right\rfloor+1$ by
considering two cases.

#### Upper bound, Case 1.

Assume that $n=4k+3$ for an integer $k\geq 1$ and consider the path
$P_{n}:v_{1}\dots v_{4k+3}$. The vertex $v_{2k+2}$ is a cut vertex and both
components of $G-v_{2k+2}$ are isomorphic to $P_{2k+1}$ where
$2k+1=\frac{n-1}{2}$. Proposition 2.5 and our hypothesis imply

$\gamma_{\rm SMB}^{\prime}(P_{n})\leq\gamma_{\rm
SMB}^{\prime}\left(P_{\frac{n-1}{2}}\right)+1=\left\lfloor\log_{2}\frac{n-1}{2}\right\rfloor+2=\left\lfloor\log_{2}(n-1)\right\rfloor+1.$

To finish the proof we add that, since $n=4k+3$ is not a power of $2$, the
equality
$\left\lfloor\log_{2}(n-1)\right\rfloor=\left\lfloor\log_{2}n\right\rfloor$
necessarily holds.

#### Upper bound, Case 2.

Assume that $n=4k+1$ for an integer $k\geq 1$ and consider the path
$P_{n}:v_{1}\dots v_{4k+1}$. Now, we choose the cut vertex $v_{2k}$ and
consider the components $P^{1}:v_{1}\dots v_{2k-1}$ and $P^{2}:v_{2k+1}\dots
v_{4k+1}$ of $P_{n}-v_{2k}$. Remark that $P^{2}$ is a path of order
$\frac{n+1}{2}$. As $\gamma_{\rm SMB}^{\prime}(P^{1})\leq\gamma_{\rm
SMB}^{\prime}(P^{2})$, Proposition 2.5 and our hypothesis together imply

$\gamma_{\rm SMB}^{\prime}(P_{n})\leq\gamma_{\rm
SMB}^{\prime}\left(P_{\frac{n+1}{2}}\right)+1=\left\lfloor\log_{2}\frac{n+1}{2}\right\rfloor+2=\left\lfloor\log_{2}(n+1)\right\rfloor+1.$

As $n+1=4k+2$ and $n+1\geq 6$, it cannot be a power of $2$ and therefore, we
get
$\left\lfloor\log_{2}(n+1)\right\rfloor=\left\lfloor\log_{2}n\right\rfloor$.
It finishes the proof for the upper bound.

#### Lower bound.

We now prove that Dominator can ensure that Staller does not win in her first
$\left\lfloor\log_{2}n\right\rfloor$ moves on the path $P_{n}:v_{1}\dots
v_{n}$. We analyze different cases according to Staller’s first move $s_{1}$.

  * •

Assume that $s_{1}=v_{i}$ for an odd integer $i\in\\{1,3,\dots,n\\}$. By
symmetry and the condition $n\geq 5$, we may suppose $i\geq 3$. Dominator then
replies by playing $d_{1}=v_{i-1}$. The remaining vertices, except $v_{i-2}$,
are covered by the following matching in $G-\\{v_{i},v_{i-1}\\}$:

$v_{1}v_{2},\dots,v_{i-4}v_{i-3},\,v_{i+1}v_{i+2},\dots,v_{n-1}v_{n}.$

As it satisfies the conditions in Lemma 5.1, we may conclude, by Lemma 5.1,
that Dominator can win the game if Staller’s first move is $v_{i}$ with an odd
index $i$.

  * •

Suppose now that $s_{1}=v_{i}$ and $i$ is even. We may also assume, without
loss of generality, that $i\leq\frac{n+1}{2}$. Dominator’s response is the
move $d_{1}=v_{i-1}$. After these two moves, by Proposition 2.1, the winning
sets for Staller are exactly the edges of the hypergraph ${\cal
H}^{\prime}=({\cal H}_{P_{n}}\\!\mid\\!v_{i})-v_{i-1}$. If $i=2$, then ${\cal
H}^{\prime}$ is isomorphic to the closed neighborhood hypergraph of the path
$P_{n-2}$ and, by the induction hypothesis, Staller needs at least
$\lfloor\log_{2}(n-2)\rfloor+1$ further moves there to win. Note that, as
$n\geq 5$, the inequality
$\lfloor\log_{2}(n-2)\rfloor+2\geq\lfloor\log_{2}n\rfloor+1$ is valid and
completes the proof for the case of $i=2$. If $i\geq 4$, then ${\cal
H}^{\prime}$ contains two components. One of them is exactly the closed
neighborhood hypergraph of the odd path $P^{2}:v_{i+1}\dots v_{n}$. Adding the
extra (hyper)edge $\\{v_{i-2},v_{i-3}\\}$ to the other component of ${\cal
H}^{\prime}$, we obtain the closed neighborhood hypergraph of the even path
$P^{1}:v_{1}\dots v_{i-2}$. Since $\gamma_{\rm SMB}^{\prime}(P^{1})=\infty$,
Proposition 2.4 and the induction hypothesis together imply that Staller needs
at least $\gamma_{\rm SMB}^{\prime}(P^{2})=\lfloor\log_{2}(n-i)\rfloor+1$
moves to win the S-game on $P^{1}\cup P^{2}$. Since ${\cal H}^{\prime}$ can be
obtained from the closed neighborhood hypergraph ${\cal H}_{P^{1}\cup P^{2}}$
by deleting the edge $\\{v_{i-2},v_{i-3}\\}$, Staller needs at least as many
moves to win on ${\cal H}^{\prime}$ as on ${\cal H}_{P^{1}\cup P^{2}}$. We may
conclude that, if Dominator plays optimally and Staller wins with her $t^{\rm
th}$ move, then

$t\geq\left\lfloor\log_{2}(n-i)\right\rfloor+2\geq\left\lfloor\log_{2}\frac{n-1}{2}\right\rfloor+2=\left\lfloor\log_{2}(n-1)\right\rfloor+1=\left\lfloor\log_{2}n\right\rfloor+1,$

where the last equality is true because $n$ cannot be a power of $2$.

This establishes the lower bound $\gamma_{\rm
SMB}^{\prime}(P_{n})\geq\left\lfloor\log_{2}n\right\rfloor+1$ and, together
with the first part of the proof, we obtain $\gamma_{\rm
SMB}^{\prime}(P_{n})=\left\lfloor\log_{2}n\right\rfloor+1$ for every odd
integer $n$. Analizing Staller’s strategy described in the proof of the upper
bound, we also infer that the claimed winning set is always one of
$N[v_{1}],N[v_{3}],\dots,N[v_{n}]$. $\square$

##  6 Tadpole graphs

The _tadpole graph_ $T(n,k)$ with parameters $n\geq 3$ and $k\geq 1$ is
obtained from an $n$-cycle and a (vertex disjoint) path of order $k$ such that
one vertex from the cycle and one end of the path are made adjacent. These
graphs have been recently studied in [9] concerning Rall’s $1/2$-conjecture
[21] on the domination game.

First we prove a short technical lemma.

###### Lemma 6.1

For every two integers $a$ and $b$ with $a\geq 1$ and $b\geq 2$, the following
is true:

$\max\\{\lfloor\log_{2}a\rfloor+1,\lceil\log_{2}(b-1)\rceil\\}\geq\lceil\log_{2}(a+b)\rceil-1.$

Proof.  Let $\lceil\log_{2}(a+b)\rceil=s$ and note that $s\geq 2$. Suppose for
a contradiction that $\lfloor\log_{2}a\rfloor+1\leq s-2$ and
$\lceil\log_{2}(b-1)\rceil\leq s-2$ simultaneously hold. These assumptions
imply $a<2^{s-2}$ and $b\leq 2^{s-2}+1$. We infer $a+b<2^{s-1}+1$ and, as
$a+b$ is an integer, we get $a+b\leq 2^{s-1}$ that contradicts the definition
of $s$. $\square$

To state the main theorem of this section, we introduce the notation

$\sigma(n)=\frac{2^{\lceil\log_{2}n\rceil}-n}{2}+1.$

###### Theorem 6.2

For every tadpole graph $T(n,k)$ it is true that $\gamma_{\rm
SMB}(T(n,k))=\infty$ and

$\gamma_{\rm
SMB}^{\prime}(T(n,k))=\begin{cases}\lceil\log_{2}(n+k+\sigma(n))\rceil&\text{
if $n$ is even and $k$ is odd};\\\ \infty&\text{otherwise}.\end{cases}$

Proof. Let $v_{0}v_{1}\dots v_{n-1}v_{0}$ and $u_{1}\dots u_{k}$ be the cycle
and the path of the tadpole graph such that $v_{0}$ and $u_{k}$ are adjacent.

We first prove that Dominator can win the D-game that is $\gamma_{\rm
SMB}(T(n,k))=\infty$ holds for every pair $(n,k)$ of positive integers with
$n\geq 3$. Let Dominator play $d_{1}=v_{0}$ as his first move. The edges

$v_{1}v_{2},\dots,v_{2\lceil n/2\rceil-3}v_{2\lceil
n/2\rceil-2},\,u_{1}u_{2},\dots,u_{2\lfloor k/2\rfloor-1}u_{2\lfloor
k/2\rfloor}$

form a matching in $T(n,k)-v_{0}$ that covers all vertices which are not
dominated by $v_{0}$. Lemma 5.1 thus implies $\gamma_{\rm
SMB}(T(n,k))=\infty$.

Next, we consider the S-game. If both $n$ and $k$ are odd or both are even,
then $T(n,k)$ has a perfect matching and Dominator can win by applying the
pairing strategy. If $n$ is odd and $k$ is even, we may iteratively remove a
weak support vertex and its leaf until a cycle $C_{n}$ remains. Thus, by
Proposition 4.1, $\gamma_{\rm SMB}^{\prime}(C_{n})\leq\gamma_{\rm
SMB}^{\prime}(T(n,k))$ is valid and then, $\gamma_{\rm
SMB}^{\prime}(C_{n})=\infty$ [12] implies $\gamma_{\rm
SMB}^{\prime}(T(n,k))=\infty$.

In the rest of the proof, we suppose that $n$ is even, $k$ is odd, and an
S-game is played on $T(n,k)$. From now on, $\ell$ denotes
$\lceil\log_{2}n\rceil$. Note that $\ell\geq 3$ unless $n=4$.

#### Upper bound

We consider three cases and show that Staller can win by playing at most
$\lceil\log_{2}(n+k+\sigma(n))\rceil$ vertices. The first two cases together
settle the proof for every tadpole graph $T(n,1)$, $n\geq 4$. Then, in Case 3,
we proceed by induction on $k$ for every fixed $n$.

#### Case 1.

$n+k+\sigma(n)\leq 2^{\ell}$.
To prove $\gamma_{\rm SMB}^{\prime}(T(n,k))\leq\ell$, consider the following
strategy of Staller. First, Staller plays $s_{1}=v_{i}$ with
$i=2\lceil\frac{n}{4}\rceil$. Observe that $v_{i}$ and $v_{0}$ split the cycle
into two nearly equal odd paths that are $P^{1}:v_{1}\dots v_{i-1}$ and
$P^{2}:v_{i+1}\dots v_{n-1}$. If $n=4p$, both paths are of order
$\frac{n}{2}-1$, and if $n=4p+2$, then $P^{1}$ is of order $\frac{n}{2}$ and
the order of $P^{2}$ is $\frac{n}{2}-2$. Note that $2\leq i\leq n-2$.

In the continuation, if Dominator’s first move $d_{1}$ is not a neighbor of
$v_{i}$, Staller selects her next move $s_{2}$ from $\\{v_{i-1},v_{i+1}\\}$
such that the distance between $s_{2}$ and $d_{1}$ is at least $3$. It can be
done as our present condition $n+k+\sigma(n)\leq 2^{\ell}$ excludes $n=4$.
Without loss of generality, we may suppose that $s_{2}=v_{i-1}$. Then, after
Dominator’s move $d_{2}$, one of $v_{i-2}$ and $v_{i+1}$ remains unplayed.
Playing this vertex as $s_{3}$, Staller can win the game by claiming
$N[v_{i}]$ or $N[v_{i-1}]$. In this case, Staller wins the game in $3\leq\ell$
moves.

If Dominator plays a neighbor of $s_{1}$ as his first move $d_{1}$, the game
continues with the winning sets in $({\cal H}_{T(n,k)}\mid s_{1})-d_{1}$.
Suppose that $d_{1}=v_{i+1}$. Deleting the winning sets
$N[v_{i+3}],\dots,N[v_{n-1}]$ from $({\cal H}_{T(n,k)}\mid s_{1})-d_{1}$, we
obtain the hypergraph ${\cal H}^{\prime}$. By Proposition 2.2, ${\rm
w}_{M}^{M}({\cal H}^{\prime})\geq{\rm w}_{M}^{M}(({\cal H}_{T(n,k)}\mid
s_{1})-d_{1})$. Note that ${\cal H}^{\prime}$ can be obtained from the closed
neighborhood hypergraph of the path $P^{\prime}:v_{i-1}\dots v_{0}u_{k}\dots
u_{1}$ by replacing the edge $\\{v_{1},v_{0},u_{k}\\}$ with
$\\{v_{1},v_{0},u_{k},v_{n-1}\\}$. Then, Staller continues playing according
to the optimal strategy on the path $P^{\prime}$ that makes sure that the
claimed winning set is either $v_{j}$ or $u_{j}$ with an odd index $j$. By
Theorem 5.2, such a winning strategy exists and it can be applied for ${\cal
H}^{\prime}$. The order of $P^{\prime}$ is at most $\frac{n}{2}+1+k$, and
therefore, Staller can win the game in at most
$1+\lceil\log_{2}(\frac{n}{2}+1+k)\rceil$ moves. We observe that

$1+\left\lceil\log_{2}\left(\frac{n}{2}+1+k\right)\right\rceil=1+\lceil\log_{2}(n+k+\sigma(n)-2^{\ell-1})\rceil\leq
1+\lceil\log_{2}(2^{\ell}-2^{\ell-1})\rceil=\ell,$

where the inequality follows from the condition $n+k+\sigma(n)\leq 2^{\ell}$.

If $d_{1}=v_{i-1}$, the argumentation is similar. Here we consider the path
$P^{\prime}:v_{i+1}\dots v_{n-1}v_{0}u_{k}\dots u_{1}$ which is of order
$n-i+k\leq\frac{n}{2}+k$.

We conclude that, under the present condition, Staller has a strategy to win
the S-game by playing at most $\ell$ vertices. Therefore, $\gamma_{\rm
SMB}^{\prime}(T(n,k))\leq\lceil\log_{2}(n+k+\sigma(n))\rceil$ holds if the
parameters $n$ and $k$ satisfy the condition in Case 1.

#### Case 2.

$n\geq 2^{\ell}-2$ and $k=1$.
As $\sigma(n)=1$ if $n=2^{\ell}$, and $\sigma(n)=2$ if $n=2^{\ell}-2$, we have
$\lceil\log_{2}(n+k+\sigma(n))\rceil=\ell+1$ under the present condition. To
show $\gamma_{\rm SMB}^{\prime}(T(n,1))\leq\ell+1$, we apply Proposition 2.5
for the cut vertex $v_{0}$. The components of $T(n,1)-v_{0}$ are an isolated
vertex with $\gamma_{\rm SMB}^{\prime}(P_{1})=1$ and an $(n-1)$-path with
$\gamma_{\rm SMB}^{\prime}(P_{n-1})=\lceil\log_{2}(n-1)\rceil=\ell.$
Proposition 2.5 therefore implies $\gamma_{\rm
SMB}^{\prime}(T(n,1))\leq\ell+1$.

#### Case 3.

$2^{s-1}<n+k+\sigma(n)\leq 2^{s}$ and $s\geq\ell+1$.
To prove $\gamma_{\rm SMB}^{\prime}(T(n,k))\leq s$ we identify appropriate cut
vertices again. If $k\leq 2^{s-1}$, we consider $T(n,k)-v_{0}$. The two
components are isomorphic to two paths, one is of order $n-1$ and the other is
of order $k$. by definition of $\ell$, we have $n-1<2^{\ell}\leq 2^{s-1}$ that
gives $\max\\{n-1,k\\}\leq 2^{s-1}$ in turn and we conclude, by Proposition
2.5 that $\gamma_{\rm SMB}^{\prime}(T(n,k))\leq(s-1)+1=s$.

If $k>2^{s-1}$, we choose the cut vertex $u_{2^{s-1}}$ and consider the two
components obtained after the removal of $u_{2^{s-1}}$. One component is a
path with $\gamma_{\rm SMB}^{\prime}(P_{2^{s-1}-1})=s-1$ while the other
component is a tadpole graph $T^{\prime}=T(n,k-2^{s-1})$. Since
$n+k+\sigma(n)\leq 2^{s}$ implies $n+k-2^{s-1}+\sigma(n)\leq 2^{s-1}$, the
induction hypothesis yields $\gamma_{\rm SMB}^{\prime}(T^{\prime})\leq s-1$.
By Proposition 2.5, we infer $\gamma_{\rm SMB}^{\prime}(T(n,k))\leq(s-1)+1=s$
again.

#### Lower bound.

In the second part, we show that

$\gamma_{\rm SMB}^{\prime}(T(n,k))\geq\lceil\log_{2}(n+k+\sigma(n))\rceil$

holds for every pair $(n,k)$ with $n\geq 4$ even and $k\geq 1$ odd. First we
eliminate some worst first moves of Staller which make possible Dominator’s
winning in the continuation. Let $s_{1}$ and $d_{1}$ denote Staller’s and
Dominator’s first move in the S-game on $T(n,k)$.

#### Case 1

$s_{1}=u_{i}$ and $i$ is odd or $s_{1}=v_{j}$ and $j$ is odd.
These are Staller’s worst first moves. We prove that, under this condition,
Dominator has a winning strategy in the continuation of the game.

  * •

If $s_{1}=u_{1}$ and $k=1$, Dominator replies by playing $d_{1}=v_{0}$. Then,
the graph $G-\\{u_{1},v_{0},v_{1}\\}$ admits a perfect matching that satisfies
the conditions of Lemma 5.1 with $X=\\{d_{1}\\}$, $Y=\\{s_{1}\\}$ and hence,
Dominator can win the continuation of the game.

  * •

If $s_{1}=u_{1}$ and $k\geq 3$, Dominator plays $d_{1}=u_{2}$. Here, we
consider the perfect matching in $G-\\{u_{1},u_{2},u_{3}\\}$ and conclude, by
Lemma 5.1, that Dominator can win.

  * •

If $s_{1}=u_{i}$ and $i$ is an odd integer with $i\geq 3$, Dominator replies
with $d_{1}=u_{i-1}$. The graph $G-\\{u_{i},u_{i-1},u_{i-2}\\}$ admits a
perfect matching and, by applying Lemma 5.1, we infer that Dominator can win
in the continuation of the game.

  * •

If $s_{1}=v_{1}$, Dominator plays $d_{1}=v_{2}$. As
$G-\\{v_{1},v_{2},v_{3}\\}$ admits a perfect matching, we conclude, by Lemma
5.1, that Dominator can win.

  * •

If $s_{1}=v_{j}$ and $j$ is an odd integer with $j\geq 3$, Dominator plays
$d_{1}=v_{j-1}$. Since the conditions of Lemma 5.1 are satisfied by the
perfect matching in $G-\\{v_{j},v_{j-1},v_{j-2}\\}$, Dominator can win the
game.

#### Case 2.

$s_{1}=v_{0}$.
If $k\leq n-1$, Dominator replies by playing $d_{1}=u_{k}$ and the
continuation of the game reduces to a Maker-Breaker game on ${\cal
H}^{\prime}=({\cal H}_{T(n,k)}\mid v_{0})-u_{k}$. If $k=1$, then ${\cal
H}^{\prime}$ is the closed neighborhood hypergraph of the path
$v_{1},\dots,v_{n-1}$. If $k\geq 3$ then, by adding $\\{u_{k-1},u_{k-2}\\}$ to
the winning sets, we obtain a hypergraph ${\cal H}^{\prime\prime}$ that
consists of two components. ${\cal H}^{\prime\prime}$ is the closed
neighborhood hypergraph of a disjoint union of a path of order $n-1$ and a
path of order $k-1$. As $k-1$ is even, $\gamma_{\rm
SMB}^{\prime}(P_{k-1})=\infty$. Applying Proposition 2.2, 2.4, and Theorem 5.2
we get

${\rm w}_{M}^{M}({\cal H}^{\prime})\geq{\rm w}_{M}^{M}({\cal
H}^{\prime\prime})=\gamma_{\rm
SMB}^{\prime}(P_{n-1})=\lceil\log(n-1)\rceil=\ell,$

no matter whether $k=1$ or $k\geq 3$. Dominator thus can force Staller to play
at least $\ell+1$ vertices in the game. On the other hand, the condition
$k\leq n-1\leq 2^{\ell}-1$ implies

$n+k+\sigma(n)=\frac{n}{2}+k+2^{\ell-1}+1\leq
2^{\ell-1}+2^{\ell}-1+2^{\ell-1}+1=2^{\ell+1}.$

Consequently, Dominator can ensure that Staller plays at least
$\lceil\log_{2}(n+k+\sigma(n))\rceil$ vertices.

Assume now that $k\geq n$. Then, Dominator replies with $d_{1}=v_{1}$ and the
game continues on ${\cal H}^{\prime}=({\cal H}_{T(n,k)}\mid v_{0})-v_{1}$.
Adding the winning set $\\{v_{2},v_{3}\\}$ to ${\cal H}^{\prime}$, we obtain
${\cal H}^{\prime\prime}$ that is the closed neighborhood hypergraph of two
disjoint paths one of them is an even path of order $n-2$ and the other one is
of order $k$. By the same reasoning as before, we get that Staller needs to
play at least $1+\lceil\log_{2}(k)\rceil$ vertices to win. If
$\ell+1\geq\lceil\log_{2}(n+k+\sigma(n))\rceil$, this already finishes the
proof as $\lceil\log_{2}(k)\rceil\geq\lceil\log_{2}(n)\rceil=\ell$. In the
other case, $\lceil\log_{2}(n+k+\sigma(n))\rceil=s\geq\ell+2$ and

$2^{s-1}<n+k+\sigma(n)=\frac{n}{2}+k+2^{\ell-1}+1.$

This, together with the condition $n/2\leq 2^{\ell-1}$ implies
$\lceil\log_{2}(k)\rceil\geq s-1$ and therefore,
$1+\lceil\log_{2}(k)\rceil\geq s$ as required.

#### Case 3.

$s_{1}=v_{i}$, $i$ is even and $i\geq 2$.
By symmetry, we may suppose that $i\geq n/2$ if $n\equiv 0\pmod{4}$ and $i\geq
n/2+1$ if $n\equiv 2\pmod{4}$. Let Dominator reply by playing $d_{1}=v_{i+1}$.
By Proposition 2.1, the game continues on ${\cal H}=({\cal H}_{T(n,k)}\mid
v_{i})-v_{i+1}$. We modify ${\cal H}$ by adding the winning set
$\\{v_{i+2},v_{i+3}\\}$ (if $i+1\neq n-1$) and replacing $N[v_{0}]$ and
$N[v_{n-1}]$ with $N[v_{0}]\setminus\\{v_{n-1}\\}$ and
$N[v_{n-1}]\setminus\\{v_{0}\\}$. The obtained hypergraph is denoted by ${\cal
H}^{\prime}$. By Proposition 2.2, ${\rm w}_{M}^{M}({\cal H}^{\prime})\leq
w_{M}^{M}({\cal H})$. Observe that ${\cal H}^{\prime}$ is the closed
neighborhood hypergraph of the graph $G^{\prime}$ that consists of two (or
only one) path components that are $P^{1}:v_{i-1}\dots v_{0}u_{k}\dots u_{1}$
and $P^{2}:v_{i+2}\dots v_{n-1}$. The component $P^{1}$ is a path of order
$i+k$ and $P^{2}$ is a path of even order. By Proposition 2.4, $\gamma_{\rm
SMB}^{\prime}(G^{\prime})=\gamma_{\rm
SMB}^{\prime}(P^{1})=\lceil\log_{2}(i+k)\rceil$. Hence, if $t$ is the number
of moves Staller needs to win when $s_{1}=v_{i}$ is fixed, then

$t\geq 1+{\rm w}_{M}^{M}({\cal H}^{\prime})=1+\gamma_{\rm
SMB}^{\prime}(P^{1})=1+\lceil\log_{2}(i+k)\rceil.$ (3)

Let $s=\lceil\log_{2}(n+k+\sigma(n))\rceil$.

  * •

If $s=\ell$, then (3) together with $i+k\geq\frac{n}{2}+1>2^{\ell-2}$ gives
$t\geq s$.

  * •

If $s=\ell+1$, we consider the inequality

$\frac{n}{2}+k=n+k+\sigma(n)-2^{\ell-1}-1>2^{\ell}-2^{\ell-1}-1=2^{\ell-1}-1.$
(4)

If $n\equiv 0\pmod{4}$, then $i\geq n/2$ and, as $n/2+k$ is odd, the strict
inequality in (4) reduces to $\frac{n}{2}+k\geq 2^{\ell-1}+1$. Then, (3) and
(4) together give $t\geq\ell+1$. If $n\equiv 2\pmod{4}$, then $i\geq 1+n/2$.
By (4), we have

$i+k\geq\frac{n}{2}+k+1>2^{\ell-1}$

and, by using (3), we conclude $t\geq s$ again.

  * •

If $s\geq\ell+2$, then $i+k>2^{s-2}$. Then, $1+\lceil\log_{2}(i+k)\rceil\geq
s$ and (3) imply the desired inequality $t\geq s$.

Remark that Cases 1–3 cover all possibilities if $k=1$. Hence, we may proceed
by induction on $k$ when the last case is considered.

#### Case 4.

$s_{1}=u_{i}$ and $i$ is even.
Applying Lemma 6.1 with $a=i-1$ and $b=n+k-i+\sigma(n)+1$ we obtain

$\begin{split}m&=\max\\{\lfloor\log_{2}(i-1)\rfloor+1,\lceil\log_{2}(n+k-i+\sigma(n))\rceil\\}\\\
&\geq\lceil\log_{2}(n+k+\sigma(n))\rceil-1.\end{split}$ (5)

If $m=\lfloor\log_{2}(i-1)\rfloor+1$, Dominator’s reply to $s_{1}=u_{i}$ is
$d_{1}=u_{i+1}$. Then, the game continues on ${\cal H}^{\prime}=({\cal
H}_{T(n,k)}\mid u_{i})-u_{i+1}$. Adding a new winning set
$\\{u_{i+2},u_{i+3}\\}$ to ${\cal H}^{\prime}$, we obtain ${\cal
H}^{\prime\prime}$. Note that playing on ${\cal H}^{\prime\prime}$ is at least
as advantageous for Staller as on ${\cal H}^{\prime}$. One component of ${\cal
H}^{\prime\prime}$ is the closed neighborhood hypergraph of a tadpole graph
$T^{\prime}=T(n,k-i-1)$. As $k-i-1$ is even, $\gamma_{\rm
SMB}^{\prime}(T^{\prime})=\infty$. The other component of ${\cal
H}^{\prime\prime}$ is the closed neighborhood hypergraph of a path of order
$i-1$. By Proposition 2.4, Staller has to play at least $m$ further vertices
to win. As (5) shows, the total number of Staller’s moves is at least
$m+1\geq\lceil\log_{2}(n+k+\sigma(n))\rceil$.

The proof is similar if $m=\lceil\log_{2}(n+k-i+\sigma(n))\rceil$. Then,
Dominator plays $d_{1}=u_{i-1}$ and then, assuming optimal strategies in the
continuation, the game is played on the closed neighborhood hypergraph of a
tadpole graph $T(n,k-i)$ and Staller has to play at least
$m+1=\lceil\log_{2}(n+k-i+\sigma(n))\rceil+1$ vertices to win. By (5), it is
at least $\lceil\log_{2}(n+k+\sigma(n))\rceil$. $\square$

##  7 Concluding remarks

$S_{4}^{1}$$S_{4}^{2}$ Figure 2: Graphs $S_{4}^{1}$ and $S_{4}^{2}$.

Concerning the largest possible finite values of the SMBD-numbers, we have the
following:

###### Proposition 7.1

Let $G$ be a graph on $n$ vertices.

  * $(i)$

If $\gamma_{\rm SMB}^{\prime}(G)<\infty$, then $\gamma_{\rm
SMB}^{\prime}(G)\leq\left\lceil\frac{n}{2}\right\rceil$.

  * $(ii)$

If $\gamma_{\rm SMB}(G)<\infty$, then $\gamma_{\rm
SMB}(G)\leq\left\lfloor\frac{n}{2}\right\rfloor.$

Moreover, both upper bounds are sharp.

Proof. Staller and Dominator alternately select vertices in the MBD game. It
readily follows that if Staller can win in an S-game or D-game, then she plays
at most $\lceil n/2\rceil$ or at most $\lfloor n/2\rfloor$ vertices,
respectively.

To show the sharpness of the upper bounds, first consider the S-game on a
subdivided star $S_{k}^{1}$ which obtained from a star $S_{k}$ by subdividing
each of its $k$ edges exactly once. Let Dominator play according the following
strategy. If Staller plays a support vertex, Dominator replies by playing the
adjacent leaf, and vice versa. If Staller plays the center of the star,
Dominator plays one of its neighbors (if possible). This strategy of Dominator
ensures that Staller cannot claim the closed neighborhood of any support
vertices or leaves. As claiming the closed neighborhood of the center needs at
least $k+1$ moves, we have $\gamma_{\rm SMB}^{\prime}(S_{k}^{1})\geq k+1$. On
the other hand, if Staller plays support vertices, it forces Dominator to
respond with playing the adjacent leaves and Staller can win the game by
playing the last leaf or the center of the star. Therefore $\gamma_{\rm
SMB}^{\prime}(S_{k}^{1})<\infty$, and by the upper bound
$\lceil\frac{n}{2}\rceil=k+1$ we conclude $\gamma_{\rm SMB}(S_{k}^{1})=k+1$.
This proves that for every odd integer $n$, there exists a graph with
$\gamma_{\rm SMB}^{\prime}=\lceil n/2\rceil$. If $n$ is even, let $k=(n-2)/2$.
Supplementing $S_{k}^{1}$ with a new vertex that is adjacent to all support
vertices, we obtain a graph $S_{k}^{2}$ on $n=2k+2$ vertices which satisfies
$\gamma_{\rm SMB}^{\prime}(S_{k}^{2})=k+1$. To obtain sharp examples for the
D-game, we may add an isolated vertex to the graphs $S_{k}^{1}$ and
$S_{k}^{2}$. $\square$

Even if the upper bounds in Proposition 7.1 are tight, we do not know sharp
examples with $\delta(G)\geq 2$. We conjecture that the inequalities can be
improved as follows.

###### Conjecture 7.2

Let $G$ be a graph $n$ vertices.

  * $(i)$

If $\gamma_{\rm SMB}^{\prime}(G)<\infty$, then $\gamma_{\rm
SMB}^{\prime}(G)\leq\left\lceil\frac{n}{2}\right\rceil-\delta(G)+1$.

  * $(ii)$

If $\gamma_{\rm SMB}(G)<\infty$, then $\gamma_{\rm
SMB}(G)\leq\left\lfloor\frac{n}{2}\right\rfloor-\delta(G)+1.$

## Acknowledgements

We are grateful to Sandi Klavžar for helpful discussions on the topic of the
manuscript. The first author acknowledges the financial support from the
Slovenian Research Agency under the project N1-0108.

## References

  * [1] J. Beck, Combinatorial Games, Cambridge Univ. Press, 2008.
  * [2] C. Berge, Hypergraphs. Combinatorics of Finite Sets, North Holland, 1989.
  * [3] S. Ben-Shimon, M. Krivelevich, B. Sudakov, Local resilience and Hamiltonicity Maker-Breaker games in random regular graphs, Combin. Probab. Comput. 20 (2011) 173–211.
  * [4] M. Borowiecki, A. Fiedorowicz, E. Sidorowicz, Connected domination game, Appl. Anal. Discrete Math. 13 (2019) 261–289.
  * [5] B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, T. Marc, B. Patkós, Zs. Tuza, M. Vizer, The variety of domination games, Aequationes Math. 93 (2019) 1085–1109.
  * [6] B. Brešar, S. Klavžar, D.F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979–991.
  * [7] B. Brešar, M.A. Henning, S. Klavžar, D.F. Rall, Domination Games Played on Graphs, SpringerBriefs in Mathematics, 2021.
  * [8] Cs. Bujtás, M.A. Henning, Zs. Tuza, Transversal game on hypergraphs and the $3/4$-conjecture on the total domination game, SIAM J. Discrete Math. 30 (2016) 1830–1847.
  * [9] Cs. Bujtás, V. Iršič, S. Klavžar, K. Xu, On Rall’s $1/2$-conjecture on the domination game. Quaest. Math. doi: 10.2989/16073606.2020.1822945
  * [10] D. Clemens, A. Ferber, M. Krivelevich, A. Liebenau, Fast strategies in Maker–Breaker games played on random boards, Combin. Probab. Comput. 21 (2012) 897–915.
  * [11] D. Clemens, M. Mikalački, How fast can Maker win in fair biased games? Discrete Math. 341 (2018) 51–66.
  * [12] E. Duchêne, V. Gledel, A. Parreau, G. Renault, Maker-Breaker domination game, Discrete Math. 343 (2020) 111955.
  * [13] P. Erdős, J.L. Selfridge, On a combinatorial game, J. Combin. Theory Ser. A 14 (1973) 298–301.
  * [14] H. Gebauer, T. Szabó, Asymptotic random graph intuition for the biased connectivity game, Random Struct. Alg. 35 (2010) 431–443.
  * [15] V. Gledel, M.A. Henning, V. Iršič, S. Klavžar, Maker-Breaker total domination game, Discrete Appl. Math. 282 (2020) 96–107.
  * [16] V. Gledel, V. Iršič, S. Klavžar, Maker-Breaker domination number, Bull. Malays. Math. Sci. Soc. 42 (2019) 1773–1789.
  * [17] D. Hefetz, M. Mikalački, M. Stojaković, Doubly biased Maker-Breaker Connectivity game, Electron. J. Combin. 19 (2012) P61.
  * [18] D. Hefetz, M. Krivelevich, M. Stojaković, T. Szabó, Positional games, Birkhäuser/Springer, Basel, 2014.
  * [19] M.A. Henning, S. Klavžar, D.F. Rall, Total version of the domination game, Graphs Combin. 31 (2015) 1453–1462.
  * [20] M.A. Henning, S. Klavžar, D.F. Rall, The $4/5$ upper bound on the game total domination number, Combinatorica 37 (2017) 223–251.
  * [21] T. James, S. Klavžar, A. Vijayakumar, The domination game on split graphs, Bull. Aust. Math. Soc. 99 (2019) 327–337.
  * [22] C.X. Kang, S. Klavžar, I.G. Yero, E. Yi, Maker-Breaker resolving game, Bull. Malays. Math. Sci. Soc. 44 (2021) 2081–2099.
  * [23] W.B. Kinnersley, D.B. West, R. Zamani, Extremal problems for game domination number, SIAM J. Discrete Math. 27 (2013) 2090–2107.
  * [24] M. Krivelevich, The critical bias for the Hamiltonicity game is $\frac{(1+o(1))n}{\ln n}$, J. Amer. Math. Soc. 24 (2011) 125–131.
  * [25] M. Stojaković, N. Trkulja, Hamiltonian Maker-Breaker games on small graphs, Exp. Math. doi:10.1080/10586458.2019.1586599.