# Thresholds for the monochromatic clique transversal game

Csilla Bujtás a,b Email<EMAIL_ADDRESS>Pakanun Dokyeesun b Email:
<EMAIL_ADDRESS>Sandi Klavžar b,c,d Email:
<EMAIL_ADDRESS>
###### Abstract

We study a recently introduced two-person combinatorial game, the
$(a,b)$-monochromatic clique transversal game which is played by Alice and Bob
on a graph $G$. As we observe, this game is equivalent to the $(b,a)$-biased
Maker-Breaker game played on the clique-hypergraph of $G$. Our main results
concern the threshold bias $a_{1}(G)$ that is the smallest integer $a$ such
that Alice can win in the $(a,1)$-monochromatic clique transversal game on $G$
if she is the first to play. Among other results, we determine the possible
values of $a_{1}(G)$ for the disjoint union of graphs, prove a formula for
$a_{1}(G)$ if $G$ is triangle-free, and obtain the exact values of
$a_{1}(C_{n}\,\square\,C_{m})$, $a_{1}(C_{n}\,\square\,P_{m})$, and
$a_{1}(P_{n}\,\square\,P_{m})$ for all possible pairs $(n,m)$.

a Faculty of Information Technology, University of Pannonia, Hungary

b Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

c Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

d Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

Keywords: clique-hypergraph; Maker-Breaker game; clique transversal game,
threshold bias.

##  1 Introduction

The _monochromatic transversal game_ (MT game), as introduced by Mendes et al.
[16], is a positional game on a hypergraph ${\cal H}$. The two players
alternately choose (play) an unplayed vertex and Alice colors it red while Bob
colors the chosen vertex blue. Alice wins if she obtains a red transversal
(vertex cover) in ${\cal H}$ and Bob wins if he colors all vertices of a
hyperedge with blue. It is called Alice-start game or Bob-start game,
respectively, if Alice or Bob is the first to play. The _monochromatic clique-
transversal game_ (MCT game) is played on the clique-hypergraph ${\cal H}_{G}$
of a graph $G$. For the sake of simplicity, we will usually refer to an MCT
game as being played on $G$ instead of ${\cal H}_{G}$. The _$(a,b)$
-monochromatic clique-transversal game_ ($(a,b)$-MCT game) follows the rules
of the MCT game, but Alice (resp. Bob) colors $a$ vertices (resp. $b$
vertices) in each of her (resp. his) turn.

The introductory paper [16] studied the $(a,b)$-MCT game on the clique-
hypergraphs of powers of cycles and paths, observing also some basic
properties of the game.111The recent conference paper [15] written by Mendes
et al. started the study of $(a,b)$-MT game played on another type of
hypergraphs, namely on the biclique hypergraphs of powers of paths and cycles.
In this paper, besides some general results we concentrate on triangle-free
graphs in general and specifically on grids, cylinder, and torus graphs.

###  1.1 Standard definitions

A _hypergraph_ ${\cal H}$ is a set system over the vertex set $V({\cal H})$.
The hyperedge set $E({\cal H})$ of ${\cal H}$ may contain any nonempty subset
of $V({\cal H})$ i.e., $E({\cal H})\subseteq 2^{V({\cal
H})}\setminus\\{\emptyset\\}$. It is clear that every simple graph can be
considered as a (2-uniform) hypergraph. A hypergraph is _simple_ , if no
hyperedge $e\in{\cal H}$ is a subset of a different $e^{\prime}\in E({\cal
H})$. The _maximum vertex degree $\Delta({\cal H})$_ of ${\cal H}$ is the
maximum number of hyperedges incident to a vertex in ${\cal H}$. A _singleton_
is a hyperedge of cardinality $1$.

A set $S\subseteq V({\cal H})$ is a _transversal_ (also called vertex cover or
hitting set) in the hypergraph ${\cal H}$, if $S$ contains at least one vertex
from each hyperedge $e\in E({\cal H})$. Further, $S$ is a _minimal
transversal_ if it contains no transversal as a proper subset. The
_transversal hypergraph_ $Tr({\cal H})$ of ${\cal H}$ is defined on the vertex
set $V({\cal H})$ and the hyperedges correspond to the minimal transversals of
${\cal H}$. As it has been stated already in Berge’s fundamental book [2],
every simple hypergraph ${\cal H}$ satisfies ${\cal H}=Tr(Tr({\cal H}))$.

In a graph $G$, a _clique_ is a complete subgraph that is inclusion-wise
maximal. The _clique-hypergraph_ ${\cal H}_{G}$ of $G$ is defined on the same
vertex set as $G$ while its hyperedges correspond to the vertex sets of the
cliques in $G$, cf. [4, 13]. Note that every isolated vertex in $G$
corresponds to a singleton in ${\cal H}_{G}$. Moreover, if $G$ is triangle-
free and contains no isolated vertices, then ${\cal H}_{G}\cong G$.

For a non-negative integer $k$, a _$k$ -independent set_ $S\subseteq V(G)$ is
a set of vertices in a graph $G$ such that the maximum degree of the subgraph
induced by $S$ is at most $k$ [5, 6, 14]. The _$k$ -independence number_ of
$G$ is the maximum cardinality of a $k$-independent set in $G$, and is denoted
by $\alpha_{k}(G)$. The $0$-independence number $\alpha_{0}(G)$ is the
independence number $\alpha(G)$ of the graph.

The _Cartesian product_ $G\,\square\,H$ of graphs $G$ and $H$ is defined on
the vertex set $V(G)\times V(H)$ such that two vertices $(g,h)$ and
$(g^{\prime},h^{\prime})$ are adjacent if either $gg^{\prime}\in E(G)$ and
$h=h^{\prime}$, or $g=g^{\prime}$ and $hh^{\prime}\in E(H)$. If $h\in V(H)$,
then the subgraph of $G\,\square\,H$ induced by the vertex set $\\{(g,h):\
g\in V(G)\\}$ is isomorphic to $G$, called a $G$-layer, and denoted with
$G^{h}$. Analogously the $H$-layers are defined and denoted with ${}^{g}\\!H$
for a fixed vertex $g\in V(G)$. (See [12] for more details on Cartesian
products.)

The disjoint union
$G\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}H$
of (disjoint) graphs $G$ and $H$ has the vertex set $V(G)\cup V(H)$ and the
edge set $E(G)\cup E(H)$. The domination number $\gamma(G)$ of a graph $G$ is
the cardinality of a smallest dominating set, that is, a set $X\subseteq V(G)$
such that each vertex from $V(G)\setminus X$ has a neighbor in $X$. $P_{n}$
and $C_{n}$ respectively stand for the path and cycle graph on $n$ vertices.
The order of the graph $G$ will be denoted by $n(G)$. The open neighborhood
and the closed neighborhood of a vertex $v$ in $G$ will be respectively
denoted by $N(v)$ and $N[v]$. For a set $S\subseteq V(G)$ we define
$N[S]=\bigcup_{v\in S}N[v]$. For every positive integer $k$, $[k]$ stands for
the set $\\{1,\ldots,k\\}$.

###  1.2 Games

The _Maker-Breaker game,_ introduced by Erdős and Selfridge [8], is played by
Maker and Breaker on a hypergraph ${\cal H}$. (For different instances of the
Maker-Breaker game see [7, 9, 10, 18].) The vertex set $V({\cal H})$ is called
the _board_ and the hyperedges of ${\cal H}$ are the winning sets. The two
players alternately choose (i.e., play) an unplayed vertex. We say that a
player _claims_ the set $S\subseteq V({\cal H})$ if he (or she) plays all
vertices from $S$. It is a _Maker-start game_ (resp.  _Breaker-start game_) if
Maker (resp. Breaker) is the first player. _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}$. The
following observation was stated in [3]:

###### Observation 1.1

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.

By comparing the definitions, it is easy to see that an MT game on ${\cal H}$
can always be considered as a Maker-Breaker game on $Tr({\cal H})$ where Alice
is Maker and Bob is Breaker. By Observation 1.1, we may infer the following
statements that give us a useful approach in our study.

###### Observation 1.2

  * $(i)$

An MT game on a hypergraph ${\cal H}$ is the same as the Maker-Breaker game on
${\cal H}$ where Maker corresponds to Bob and Breaker corresponds to Alice.

  * $(ii)$

An $(a,b)$-MCT game on $G$ is the same as the $(b,a)$-biased Maker-Breaker
game on ${\cal H}_{G}$ where Maker is Bob and Breaker is Alice.

For a graph $G$ and a fixed positive integer $\ell$, the _threshold bias_ (or
shortly threshold) $a_{\ell}(G)$ (resp. $a_{\ell}^{\prime}(G)$) denotes the
smallest positive integer $a$ such that Alice can win in the Alice-start
(resp. Bob-start) $(a,\ell)$-MCT game. By definition, if $a<a_{\ell}(G)$, then
Bob has a winning strategy in the Alice-start $(a,\ell)$-MCT game on $G$. It
is also known (see e.g., Exercise 3.6.2 in [11]) that for every $a\geq
a_{\ell}(G)$, Alice wins in the Alice-start $(a,\ell)$-MCT game. The same is
true for the threshold $a_{\ell}^{\prime}(G)$ that is, Alice wins in the Bob-
start $(a,\ell)$-MCT game on $G$ if and only if $a\geq a_{\ell}^{\prime}(G)$.

#### Structure of the paper.

In the next subsection, we continue by observing some further basic properties
of the $(a,b)$-MCT game. Section 2 is devoted to triangle-free graphs, where
we prove general formulas for the thresholds $a_{1}(G)$ and
$a_{1}^{\prime}(G)$ if $G$ is triangle-free. Then, in Section 3, we establish
lower and upper bounds on
$a_{1}(G_{1}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}G_{2})$
in terms of $a_{1}(G_{1})$ and $a_{1}(G_{2})$ and afterwards, we show that all
values between the lower and upper bounds are realizable. The theorems in
Section 4 give a complete picture on the exact values of thresholds
$a_{1}(C_{n}\,\square\,C_{m})$, $a_{1}(C_{n}\,\square\,P_{m})$,
$a_{1}(P_{n}\,\square\,P_{m})$, and $a_{1}^{\prime}(C_{n}\,\square\,C_{m})$,
$a_{1}^{\prime}(C_{n}\,\square\,P_{m})$,
$a_{1}^{\prime}(P_{n}\,\square\,P_{m})$.

###  1.3 Preliminaries

It can be proved via different simple approaches (see e.g., Proposition 2.1.6
in [11]) that if Maker (resp. Breaker) can win as a second player in a Maker-
Breaker game on ${\cal H}$, she (resp. he) can also win as a first player. It
can be checked that the analogous proofs work for the $(a,b)$-biased Maker-
Breaker game. By Observation 1.2, we may state the same property for the
$(a,b)$-MCT game that was already mentioned in [16] as Remark 2.1.

###### Observation 1.3

If there exists a winning strategy for Alice (resp. Bob) in the Bob-start
(resp. Alice-start) $(a,b)$-MCT game on a graph $G$, then there exists a
winning strategy for Alice (resp. Bob) when she (resp. he) starts the game on
$G$.

Observation 1.3 and the definition of the threshold bias directly implies the
following relation.

###### Observation 1.4

It holds for every graph $G$ that

$a_{1}^{\prime}(G)\geq a_{1}(G)\,.$ (1)

In the rest of the paper we will also refer to the following statements.

###### Observation 1.5

  * $(i)$

If a hypergraph ${\cal H}$ contains no singletons, then Breaker has a winning
strategy in the $(1,\Delta({\cal H}))$-biased Maker-Breaker game on ${\cal H}$
no matter who is the first player.

  * $(ii)$

Let $G$ be an isolate-free graph. If each vertex belongs to at most $k$
cliques in $G$, then Alice has a winning strategy in the $(k,1)$-MCT game on
$G$ no matter who is the first player.

  * $(iii)$

If $G$ is an isolate-free graph and every vertex belongs to at most $k$
cliques in $G$, then $a_{1}(G)\leq a_{1}^{\prime}(G)\leq k$.

Proof.  In the $(1,\Delta({\cal H}))$-biased Maker-Breaker game on ${\cal H}$,
Breaker may reply to Maker’s every move $v$ by playing an unplayed vertex from
each hyperedge incident to $v$ (and some additional vertices if necessary).
This strategy ensures that whenever Maker plays a second vertex from some
hyperedge, at least one vertex from this hyperedge has been already played by
Breaker. Then, as ${\cal H}$ contains no singletons, Maker cannot win, no
matter who starts the game. This proves $(i)$.

By Observation 1.2(ii), we may conclude statement $(ii)$ from $(i)$. The last
part $(iii)$ then follows by the definition of the thresholds. $\square$

##  2 Thresholds for triangle-free graphs

In this section we focus on triangle-free graphs that do not contain isolated
vertices. For such a graph $G$, the clique hypergraph ${\cal H}_{G}$ is
isomorphic to $G$ and therefore, by Observation 1.2(ii), Bob wins the
$(a,b)$-MCT game on $G$ if and only if he claims two adjacent vertices.

###### Theorem 2.1

If $G$ is a triangle-free graph that contains no isolated vertex, then

$\displaystyle(i)\quad$ $\displaystyle a_{1}(G)=\min_{k\geq
0}\max\\{k,n(G)-\alpha_{k}(G)\\}=\min_{X\subseteq
V(G)}\max\\{\Delta(G-X),|X|\\}\,,$ $\displaystyle(ii)\quad$ $\displaystyle
a_{1}^{\prime}(G)=\Delta(G)\,.$

Proof. To establish (i), we are going to prove three claims.

###### Claim 1

If $\displaystyle a\geq\min_{k\geq 0}\max\\{k,n(G)-\alpha_{k}(G)\\}$, then
Alice wins in the $(a,1)$-MCT game.

Proof.  Alice chooses a maximum $k^{*}$-independent set $Y$ such that

$\max\\{k^{*},n(G)-\alpha_{k^{*}}(G)\\}=\min_{k\geq
0}\max\\{k,n(G)-\alpha_{k}(G)\\}.$

Observe that, by our condition, the set $X=V(G)\setminus Y$ contains at most
$a$ vertices. In the first turn, Alice plays all vertices from $X$ and further
$a-|X|$ arbitrarily chosen vertices if $a>|X|$. Since $Y$ is a
$k^{*}$-independent set, $\Delta(G[Y])\leq k^{*}\leq a$; that is each vertex
played by Bob in his first turn or later would have at most $a$ unplayed
neighbors. Alice thus can reply to each move $v$ of Bob by claiming all the
unplayed neighbors of $v$ (and some further vertices if $a$ is big enough).
With this strategy, Alice ensures that Bob can never claim two adjacent
vertices and Alice’s moves form a vertex cover that is a clique transversal in
the isolate-free graph $G$. ($\Box$)

###### Claim 2

If $a<\displaystyle\min_{X\subseteq V(G)}\max\\{\Delta(G-X),|X|\\}$, then Bob
wins in the $(a,1)$-MCT game.

Proof.  Let $A_{1}$ be the set of the $a$ vertices played by Alice in the
first turn. Under the present condition,
$a<\max\\{\Delta(G-A_{1}),|A_{1}|\\}$. As $|A_{1}|=a$, we may infer $1\leq
a<\Delta(G-A_{1})$. Consequently, in his first turn, Bob can play a vertex $v$
such that $\deg_{G-A_{1}}(v)>a$. Then, Alice cannot claim all the unplayed
neighbors of $v$ in her next turn and Bob wins in his second turn by claiming
an unplayed neighbor of $v$. ($\Box$)

###### Claim 3

For every graph $G$

$\min_{X\subseteq V(G)}\max\\{\Delta(G-X),|X|\\}=\min_{k\geq
0}\max\\{k,n(G)-\alpha_{k}(G)\\}.$

Proof.  Let $k^{*}$ be the smallest integer such that

$\max\\{k^{*},n(G)-\alpha_{k^{*}}(G)\\}=\min_{k\geq
0}\max\\{k,n(G)-\alpha_{k}(G)\\}.$

We select a maximum $k^{*}$-independent set $Y^{*}$ and define
$X^{*}=V(G)\setminus Y^{*}$. By the choice of $k^{*}$ and $Y^{*}$, we have
$|X^{*}|=n(G)-\alpha_{k^{*}}(G)$ and $\Delta(G-X^{*})=k^{*}$. This gives

$\max\\{\Delta(G-X^{*}),|X^{*}|\\}=\max\\{k^{*},n(G)-\alpha_{k^{*}}(G)\\}=\min_{k\geq
0}\max\\{k,n(G)-\alpha_{k}(G)\\}$

and, as $X^{*}\subseteq V(G)$, we conclude

$\min_{X\subseteq V(G)}\max\\{\Delta(G-X),|X|\\}\leq\min_{k\geq
0}\max\\{k,n(G)-\alpha_{k}(G)\\}.$

To prove the other direction, let $X^{\prime}$ be a set of vertices in $G$
such that

$\max\\{\Delta(G-X^{\prime}),|X^{\prime}|\\}=\min_{X\subseteq
V(G)}\max\\{\Delta(G-X),|X|\\}.$ (2)

From the possible candidates for the role of $X^{\prime}$ we choose one of
minimum cardinality. This ensures that $Y^{\prime}=V(G)\setminus X^{\prime}$
is a maximum $k^{\prime}$-independent set with
$k^{\prime}=\Delta(G-X^{\prime})$. Note that
$|X^{\prime}|=n(G)-\alpha_{k^{\prime}}(G)$ also follows and (2) remains true.
We therefore obtain

$\min_{X\subseteq
V(G)}\max\\{\Delta(G-X),|X|\\}=\max\\{k^{\prime},n(G)-\alpha_{k^{\prime}}(G)\\}\geq\min_{k\geq
0}\max\\{k,n(G)-\alpha_{k}(G)\\}$

that completes the proof of the claim. ($\Box$)

Claims 1–3 directly imply that the threshold stated in (i) holds for every
triangle- and isolate-free graph.

To prove (ii), we consider the Bob-start $(a,1)$-MCT game on $G$. As the graph
is isolate-free, Bob cannot win in his first turn. If $a<\Delta(G)$, Bob plays
a vertex $v$ of maximum degree in the first turn. As $a<\deg(v)$, Alice cannot
claim all vertices from $N(v)$ in her response and hence, Bob can win the game
in his second turn by playing an unplayed vertex which is adjacent to $v$.
This shows that $a_{1}^{\prime}(G)\geq\Delta(G)$ holds. Under the present
conditions, every clique of $G$ is an edge and therefore, Observation 1.5(iii)
implies $a_{1}^{\prime}(G)\leq\Delta(G)$. This completes the proof of (ii).
$\square$

Notice that, independently of Observation 1.3, Theorem 2.1 directly implies
$a_{1}(G)\leq a_{1}^{\prime}(G)$ for every isolate- and triangle-free graph
$G$. Indeed, by selecting $X=\emptyset$ we obtain

$a_{1}(G)\leq\max\\{\Delta(G-\emptyset),|\emptyset|\\}=\Delta(G)=a_{1}^{\prime}(G).$

###### Remark 2.2

If $G$ is triangle-free but contains $\ell\geq 1$ isolated vertices, then Bob
wins the Bob-start $(a,1)$-MCT game by claiming a clique $K_{1}$ in his first
turn. As it is true for every integer $a$, the threshold $a_{1}^{\prime}(G)$
does not exist. If Alice wins the Alice-start game, she has to play all
isolated vertices in her first turn. A further argument analogous to the proof
of Theorem 2.1 yields the following formula:

$\displaystyle a_{1}(G)$ $\displaystyle=\min_{k\geq
0}\max\\{k,\ell+n(G^{\prime})-\alpha_{k}(G^{\prime})\\},$

where $G^{\prime}$ denotes the graph obtained from $G$ by deleting all
isolated vertices. As $n(G)=n(G^{\prime})+\ell$ and
$\alpha_{k}(G)=\alpha_{k}(G^{\prime})+\ell$, we may conclude the following
equality:

$\displaystyle a_{1}(G)$ $\displaystyle=\min_{k\geq
0}\max\\{k,\ell+n(G)-\alpha_{k}(G)\\}.$

##  3 Disjoint union of graphs

###### Proposition 3.1

If $G_{1}$ and $G_{2}$ are graphs, then

$\max\\{a_{1}(G_{1}),a_{1}(G_{2})\\}\leq
a_{1}(G_{1}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}G_{2})\leq
a_{1}(G_{1})+a_{1}(G_{2})\,.$ (3)

Proof. Let $a_{1}(G_{1})=k_{1}$, $a_{1}(G_{2})=k_{2}$, and set
$G=G_{1}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}G_{2}$.
Assume without loss of generality that $k_{1}\geq k_{2}$.

Consider the $(a,1)$-MCT game on $G$. Assume first that $a<k_{1}$. In the
first move Alice selects at most $a<k_{1}$ vertices from $G_{1}$, hence Bob
has the following winning strategy. He will play only on $G_{1}$ as long as it
is possible, following his winning strategy on $G_{1}$. Since
$a<a_{1}(G_{1})=k_{1}$, Bob indeed has such a strategy. In this way, Bob also
wins on $G$. It follows that $a_{1}(G)\geq k_{1}$ which proves the lower
bound.

To prove the upper bound, we need to show that Alice has a winning strategy if
$a=k_{1}+k_{2}$. In this case, Alice follows her winning strategies on $G_{1}$
and $G_{2}$. More precisely, in the first move, she selects $k_{1}$ vertices
from $G_{1}$ and $k_{2}$ vertices from $G_{2}$ according to her strategies on
$G_{1}$ and $G_{2}$, respectively. In the rest of the game, after each move of
Bob in $G_{i}$, $i\in[2]$, she replies by selecting optimally $k_{i}$ vertices
in $G_{i}$ and arbitrary additional $k_{3-i}$ vertices from $G_{i}$. In this
way Alice wins the game and hence $a_{1}(G)\leq a_{1}(G_{1})+a_{1}(G_{2})$.
$\square$

Recall that a caterpillar is a tree in which a single path is incident to (or
contains) every edge. This single path of the caterpillar is called the spine
[19]. For $m\geq 1$ and $\ell\geq 0$ let $T_{m,\ell}$ be the caterpillar whose
spine has $m$ vertices and to each vertex of the spine, exactly $\ell$ leaves
are attached.

In the next result we determine the threshold $a_{1}$ for the caterpillars
$T_{m,\ell}$. As $T_{m,0}$ is a path of order $m$ and $a_{1}(P_{m})$ was
already established in [16], we will assume $\ell\geq 1$ here.

###### Theorem 3.2

If $m$ and $\ell$ are positive integers, then

$\displaystyle a_{1}(T_{m,\ell})=\begin{cases}m;&m\leq\ell,\\\
\ell;&\lfloor\frac{m}{2}\rfloor\leq\ell<m,\\\
\ell+1;&\lfloor\frac{m}{3}\rfloor-1\leq\ell\leq\lfloor\frac{m}{2}\rfloor-1,\\\
\ell+2;&\ell\leq\lfloor\frac{m}{3}\rfloor-2.\end{cases}$

Proof. Let $X=\\{v_{1},\ldots,v_{m}\\}$ be the set of the (consecutive)
vertices in the spine of $T_{m,\ell}$. We distinguish four cases depending on
the size of $\ell$ with respect to $m$.

#### Case 1:

$m\leq\ell$.
Note that $|X|=m$ and $\Delta(T_{m,\ell}-X)=0$, hence Theorem 2.1(i) implies
that $a_{1}(T_{m,l})\leq m$.

To prove that $a_{1}(T_{m,\ell})\geq m$, we need to show that Bob wins the
Alice-start $(a,1)$-MCT game on $T_{m,\ell}$, when $a<m$. Partition
$V(T_{m,\ell})$ into sets $V_{i}$, $i\in[m]$, where $V_{i}$ contains $v_{i}$
and all the leaves attached to it. Let $A_{1}$ be the set of $a$ vertices
played by Alice in her first move. Then there exists $i\in[m]$ such that
$A_{1}\cap V_{i}=\emptyset$. Let Bob reply by playing the vertex $v_{i}$.
Since $a<m\leq\ell$, Alice cannot claim all the neighbors of $v_{i}$ in her
next turn and hence Bob can win the game. We conclude that
$a_{1}(T_{m,\ell})\geq m$.

#### Case 2:

$\lfloor\frac{m}{2}\rfloor\leq\ell<m$.
To show that $a_{1}(T_{m,\ell})\leq\ell$, let
$Y=\\{v_{2},v_{4},\ldots,v_{2\lfloor\frac{m}{2}\rfloor}\\}\cup Y^{\prime}$,
where $Y^{\prime}$ contains $\ell-\lfloor\frac{m}{2}\rfloor$ arbitrary
additional vertices of $T_{m,\ell}$. Then $|Y|=\ell$ and
$\Delta(T_{m,\ell}-Y)=\ell$, hence using Theorem 2.1(i) we get
$a_{1}(T_{m,l})\leq\ell$.

To prove $a_{1}(T_{m,\ell})\geq\ell$, we need to show that Bob wins the Alice-
start $(a,1)$-MCT game on $T_{m,\ell}$, when $a<\ell$. For this sake partition
$V(T_{m,\ell})$ just as in Case 1 into the sets $V_{i}$, $i\in[m]$. If $A_{1}$
is the set of $a$ vertices played by Alice in her first move, then since
$a<\ell<m$ there exists $i\in[m]$ such that $A_{1}\cap V_{i}=\emptyset$. Then
Bob replies by playing $v_{i}$ and wins the game in the next turn. We conclude
that $a_{1}(T_{m,\ell})\geq\ell$.

#### Case 3:

$\lfloor\frac{m}{3}\rfloor-1\leq\ell\leq\lfloor\frac{m}{2}\rfloor-1$.
Since $\ell\geq 1$, in this case we have $m\geq 4$. To show that
$a_{1}(T_{m,\ell})\leq\ell+1$, let
$Z=\\{v_{3},v_{6},\ldots,v_{3\lfloor\frac{m}{3}\rfloor}\\}$. Then
$|Z|\leq\ell+1$ and $\Delta(T_{m,\ell}-Z)\leq\ell+1$. Therefore,
$\max\\{|Z|,\Delta(T_{m,\ell}-Z)\\}\leq\ell+1$. Applying Theorem 2.1(i) again
we obtain $a_{1}(T_{m,l})\leq\ell+1$.

Next, consider the Alice-start $(a,1)$-MCT game on $T_{m,\ell}$, when
$a<\ell+1$. Partition $V(T_{m,\ell})$ into sets $V_{i}$,
$i\in[\lfloor\frac{m}{2}\rfloor]$, where $V_{i}$ contains $v_{2i-1},v_{2i}$
and the leaves attached to both of them. When $m$ is odd,
$V_{\lfloor\frac{m}{2}\rfloor}$ also contains $v_{m}$ and all the leaves
attached to it. Let $A_{1}$ be the $a$ vertices played by Alice in her first
move. Since
$a<\ell+1\leq(\lfloor\frac{m}{2}\rfloor-1)+1=\lfloor\frac{m}{2}\rfloor$, by
the Pigeonhole principle there exists $i\in[\lfloor\frac{m}{2}\rfloor]$ such
that $A_{1}\cap V_{i}=\emptyset$. Then Bob can play the vertex $v_{2i-1}$.
Since neither the vertex $v_{2i}$ nor the leaves attached to $v_{2i-1}$ have
been played, Bob wins the game in his next move. We conclude that
$a_{1}(T_{m,\ell})\geq\ell+1$.

#### Case 4:

$\ell\leq\lfloor\frac{m}{3}\rfloor-2$.
Since $\ell\geq 1$, in this case we have $m\geq 9$. To prove the first
direction of the statement, we refer to Theorem 2.1 which implies

$a_{1}(T_{m,\ell})\leq a_{1}^{\prime}(T_{m,\ell})=\Delta(T_{m,\ell})=\ell+2.$

Consider now the Alice-start $(a,1)$-MCT game on $T_{m,\ell}$, where
$a<\ell+2$. Partition $V(T_{m,\ell})$ into sets $V_{i}$,
$i\in[\lfloor\frac{m}{3}\rfloor]$, where $V_{i}$ contains
$v_{3i-2},v_{3i-1},v_{3i}$, and all their leaves. If $3\nmid m$, then add to
$V_{\lfloor\frac{m}{3}\rfloor}$ also the (one or two) vertices $v_{j}$, where
$j>3\lfloor\frac{m}{3}\rfloor$, as well as all the leaves attached to them.
Let $A_{1}$ be the $a$ vertices played by Alice in her first move. Since
$a<\ell+2\leq\lfloor\frac{m}{3}\rfloor$, there exists
$i\in[\lfloor\frac{m}{3}\rfloor]$ such that $A_{1}\cap V_{i}=\emptyset$. Then
Bob can play $v_{3i-1}$. Since neither $v_{3i-2}$ nor $v_{3i}$ nor any leaf
attached to $v_{3i-1}$ were played by now, Bob wins the game in the next turn.
We conclude that $a_{1}(T_{m,\ell})\geq\ell+2$. $\square$

Note that the first case of Theorem 3.2, that is $a_{1}(T)=m$, also holds for
caterpillars $T$ which are obtained from $T_{m,m}$ by attaching some further
leaves (without any restrictions) to the vertices of the spine.

###### Proposition 3.3

If $1\leq\ell\leq k$ and $0\leq i\leq\ell$, then
$a_{1}(T_{k,k+i}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}T_{\ell,k+i})=k+i$.

Proof. For this proof set $T_{1}=T_{k,k+i}$, $T_{2}=T_{\ell,k+i}$, and
$T=T_{1}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}T_{2}$.
Let $v_{1},\ldots,v_{k}$ and $u_{1},\ldots,u_{\ell}$ be the consecutive
vertices of the spines of $T_{1}$ and $T_{2}$, respectively.

First we set

$X=\\{v_{2},v_{4},\ldots,v_{2\lfloor
k/2\rfloor},u_{2},u_{4},\ldots,u_{2\lfloor\ell/2\rfloor}\\}$

and observe that $|X|=\lfloor k/2\rfloor+\lfloor\ell/2\rfloor\leq k$ and
$\Delta(T-X)=k+i$ hold. Theorem 2.1 then implies
$a_{1}(T)\leq\max\\{k,k+i\\}=k+i$.

Consider now the Alice-start $(a,1)$-MCT game on $T$, when $a<k+i$. Let
$A_{1}$ be the set of vertices played by Alice in her first move. Then
$|A_{1}|=a$. Because $a<k+i\leq k+\ell$, by an argument parallel to the one
from the proof of Theorem 3.2 we infer that there exists a non-leaf $x$ from
$T$ (so $x=u_{i}$ or $x=v_{j}$) such that neither $x$ nor any leaves attached
to $x$ belong to $A_{1}$. Bob can then play $x$, and Alice cannot claim all
its neighbors in her second move. Thus Bob wins the game and $a_{1}(T)\geq
k+i$ follows. $\square$

The following result shows that both inequalities in (3) are sharp and,
moreover, every integer between the lower and the upper bound may be the value
of
$a_{1}(G_{1}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}G_{2})$
for appropriately chosen graphs.

###### Corollary 3.4

For every three integers $\ell$, $k$, and $p$ satisfying $1\leq\ell\leq k\leq
p\leq\ell+k$, there exist caterpillars $G_{1}$ and $G_{2}$ such that

$\max\\{a_{1}(G_{1}),a_{1}(G_{2})\\}=k,\quad
a_{1}(G_{1}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}G_{2})=p,\enskip\mbox{and}\enskip
a_{1}(G_{1})+a_{1}(G_{2})=k+\ell\,.$

Proof. Let us consider the caterpillars $G_{1}=T_{k,p}$ and
$G_{2}=T_{\ell,p}$. As $1\leq\ell\leq k\leq p$, $a_{1}(G_{1})=k$ and
$a_{1}(G_{2})=\ell$ hold by Theorem 3.2. This already shows
$\max\\{a_{1}(G_{1}),a_{1}(G_{2})\\}=k$ and
$a_{1}(G_{1})+a_{1}(G_{2})=k+\ell$. To prove the second equality, we set
$i=p-k$ and observe that $0\leq i\leq\ell$ holds under the present conditions.
It follows from Proposition 3.3 that
$a_{1}(G_{1}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}G_{2})=k+i=p$.
This completes the proof. $\square$

##  4 Cartesian product of paths and cycles

Throughout this section, let $V(C_{n})=[n]$ for $n\geq 3$, and let
$V(P_{n})=[n]$ for $n\geq 1$, where $1$ and $n$ are end vertices of $P_{n}$.
Moreover, for $C_{n}$ we will consider indices modulo $n$.

###  4.1 Torus graphs

In this subsection we prove:

###### Theorem 4.1

If $m\geq n\geq 3$, then

$\displaystyle a_{1}(C_{n}\,\square\,C_{m})=\begin{cases}1;&n=m=3,\\\
2;&n=3,m=4,\\\ 3;&n=3,m\geq 5,\\\ 4;&m\geq n\geq 4,\end{cases}$

and

$\displaystyle a_{1}^{\prime}(C_{n}\,\square\,C_{m})=\begin{cases}1;&n=m=3,\\\
3;&n=3,m\geq 4,\\\ 4;&m\geq n\geq 4.\end{cases}$

Proof. Consider first the case $m\geq n\geq 4$ and recall that
$V(C_{n}\,\square\,C_{m})=\\{(i,j):\ i\in[n],j\in[m]\\}$. Then
$C_{n}\,\square\,C_{m}$ is a 4-regular, triangle-free graph, hence Theorem
2.1(ii) implies $a^{\prime}_{1}(C_{n}\,\square\,C_{m})=4$. Thus by (1),
$a_{1}(C_{n}\,\square\,C_{m})\leq a^{\prime}_{1}(C_{n}\,\square\,C_{m})=4$.

It remains to show that $a_{1}(C_{n}\,\square\,C_{m})\geq 4$. For this sake
consider the following winning strategy for Bob in the Alice-start $(3,1)$-MCT
game on $C_{n}\,\square\,C_{m}$. Let $A_{1}$ be the set of three vertices
played by Alice in her first move. Since we have assumed that $m\geq n\geq 4$,
there exist $i\in[n]$ and $j\in[m]$ such that $A_{1}\cap
V((C_{n})^{j})=\emptyset$ and $A_{1}\cap V(^{i}(C_{m}))=\emptyset$. Then Bob
plays $(i,j)$ in his first move. Since $(i,j)$ is adjacent to four unplayed
vertices, Alice cannot claim all these vertices in her next turn. Therefore
Bob can win by playing an unplayed neighbor of $(i,j)$. This finishes the
proof for $m\geq n\geq 4$.

In the rest of the proof we assume that $n=3$ and consider the $(a,1)$-MCT
game on $C_{3}\,\square\,C_{m}$.

#### Case 1:

$m=3$.
Consider the Bob-start $(1,1)$-MCT game on $C_{3}\,\square\,C_{3}$. By
symmetry we may assume without loss of generality that the first move of Bob
is $(1,1)$. Then Alice replies by the move $(2,1)$. Then, using symmetry
again, we need to consider four cases for a possible second move of Bob:
$(1,2)$, $(2,2)$, $(3,2)$, and $(3,1)$. If Bob plays $(1,2)$, Alice replies by
$(1,3)$. Then the only layers in which Alice has not played yet are
$(C_{3})^{2}$ and ${}^{3}(C_{3})$. Whatever Bob plays next, Alice replies in
the layer $(C_{3})^{2}$ and later she can finish the game with a move in
${}^{3}(C_{3})$. In all the other possible second moves of Bob, Alice replies
by playing $(1,2)$ and then the only layers in which Alice has not played yet
are $(C_{3})^{3}$ and ${}^{3}(C_{3})$. Then it is straightforward to see that
in all the cases Alice can win the game. We conclude that
$a^{\prime}_{1}(C_{3}\,\square\,C_{3})=1$ and by Observation 1.3 also
$a_{1}(C_{3}\,\square\,C_{3})=1$.

#### Case 2:

$m=4$.
Since each vertex is incident with three cliques (one $3$-cycle and two
edges), Observation 1.5(iii) yields $a^{\prime}_{1}(C_{3}\,\square\,C_{4})\leq
3$.

Consider the Bob-start $(2,1)$-MCT game on $C_{3}\,\square\,C_{4}$. Let Bob
choose $(2,2)$ in his first move. Then Alice must play the vertices $(2,1)$
and $(2,3)$, for otherwise Bob can claim an edge in the layer ${}^{2}(C_{4})$
in his next move. Then Bob replies with $(1,2)$. As Alice cannot play all the
three vertices $(3,2)$, $(1,1)$, and $(1,3)$ in her next move, Bob can claim a
clique in his second move. Thus $a^{\prime}_{1}(C_{3}\,\square\,C_{4})\geq 3$.
We conclude that $a^{\prime}_{1}(C_{3}\,\square\,C_{4})=3$.

Next we consider the Alice-start $(2,1)$-MCT game on $C_{3}\,\square\,C_{4}$.
To show that $a_{1}(C_{3}\,\square\,C_{4})\leq 2$, we will give a winning
strategy for Alice. Let her start the game by playing $(1,1)$ and $(2,3)$.
Assume that Bob plays a vertex $(i,j)$. If $(i,j)$ is in $(C_{3})^{1}$ or in
$(C_{3})^{3}$, then Alice responds by playing two neighbors of $(i,j)$ in
${}^{i}(C_{4})$, and then Bob cannot claim any clique incident to $(i,j)$. As
Alice has already played a vertex from each $C_{3}$, in the continuation,
after any move $(i^{\prime},j^{\prime})$ of Bob, Alice can reply by choosing
the (at most two) unplayed neighbors in ${}^{i^{\prime}}(C_{4})$, and she wins
the game. In the second case suppose that Bob’s first move $(i,j)$ is from
$(C_{3})^{2}$ or $(C_{3})^{4}$. If $(i,j)\in\\{(1,2),(1,4),(2,2),(2,4)\\}$,
then Alice replies by choosing one neighbor of $(i,j)$ in $(C_{3})^{j}$ and
the neighbor of $(i,j)$ in ${}^{i}(C_{4})$ which was not yet selected. One can
now check easily that Alice can win the game. The remaining subcase is
$(i,j)=(3,2)$ (or symmetrically $(i,j)=(3,4)$). Then Alice responds by
choosing $(3,1)$ and $(3,3)$. In each case it is now easy to see that Alice
will win the game. This shows that $a_{1}(C_{3}\,\square\,C_{4})\leq 2$.

It remains to prove that $a_{1}(C_{3}\,\square\,C_{4})\geq 2$ by providing a
winning strategy for Bob in the $(1,1)$-MCT game. Assume that Alice first
plays $(i,j)$. Then Bob replies by playing $(i^{\prime},j^{\prime})$, where
$i^{\prime}\neq i$ and $j^{\prime}\neq j$, and can win the game in his second
move. We conclude that $a_{1}(C_{3}\,\square\,C_{4})=2$.

#### Case 3:

$m\geq 5$.
By Observation 1.5(iii), $a_{1}(C_{3}\,\square\,C_{m})\leq 3$.

To show that $a_{1}(C_{3}\,\square\,C_{m})\geq 3$, we will show that Bob has a
winning strategy in the Alice-start $(2,1)$-MCT game on
$C_{3}\,\square\,C_{m}$. Assume that Alice plays two vertices in her first
move. Then there are two consecutive layers $(C_{3})^{k}$ and $(C_{3})^{k+1}$
such that no vertex in these layers was played by Alice. By symmetry we may
assume that the vertices $(1,k-1)$ and $(2,k-1)$ were not selected by Alice.
Then Bob replies by selecting the vertex $(1,k)$. This forces Alice to reply
by playing $(1,k-1)$ and $(1,k+1)$. Then Bob plays $(2,k)$ which forces Alice
to play $(2,k-1)$ and $(2,k+1)$. Now Bob wins by playing $(3,k)$. Hence
$a_{1}(C_{3}\,\square\,C_{m})\geq 3$ and consequently
$a_{1}(C_{3}\,\square\,C_{m})=3$.

By Observation 1.5(iii), we have $3=a_{1}(C_{3}\,\square\,C_{m})\leq
a_{1}^{\prime}(C_{3}\,\square\,C_{m})\leq 3$. We conclude that
$a_{1}^{\prime}(C_{3}\,\square\,C_{m})=3$. $\square$

###  4.2 Cylinder graphs

In this subsection we consider cylinder graphs, that is, Cartesian products of
paths by cycles. The result reads as follows.

###### Theorem 4.2

If $n\geq 3$ and $m\geq 2$, then

$\displaystyle a_{1}(C_{n}\,\square\,P_{m})=\begin{cases}2;&n=3,\ 2\leq m\leq
5,\text{or\ }\\\ &n=4,\ m=2,\\\ 3;&n=3,\ m\geq 6,\text{or\ }\\\ &n=4,\ 3\leq
m\leq 5,\text{or\ }\\\ &n=5,\ 2\leq m\leq 4,\text{or\ }\\\ &6\leq n\leq 9,\
m=2,3,\text{or\ }\\\ &n\geq 10,\ m=2,\\\ 4;&\text{otherwise}.\end{cases}$

and

$\displaystyle a_{1}^{\prime}(C_{n}\,\square\,P_{m})=\begin{cases}2;&n=3,\
m=2,\\\ 3;&n=3,\ m\geq 3,\text{or\ }\\\ &n\geq 4,\ m=2,\\\ 4;&n\geq 4,\ m\geq
3.\end{cases}$

$n\backslash m$ |  2 |  3 |  4 |  5 | $\geq 6$
---|---|---|---|---|---
3 | 2 | 2 | 2 | 2 | 3
4 | 2 | 3 | 3 | 3 | 4
5 | 3 | 3 | 3 | 4 | 4
6 | 3 | 3 | 4 | 4 | 4
7 | 3 | 3 | 4 | 4 | 4
8 | 3 | 3 | 4 | 4 | 4
9 | 3 | 3 | 4 | 4 | 4
$\geq 10$ | 3 | 4 | 4 | 4 | 4

$n\backslash m$ |  2 |  3 |  4 |  5 | $\geq 6$
---|---|---|---|---|---
3 | 2 | 3 | 3 | 3 | 3
4 | 3 | 4 | 4 | 4 | 4
5 | 3 | 4 | 4 | 4 | 4
6 | 3 | 4 | 4 | 4 | 4
7 | 3 | 4 | 4 | 4 | 4
8 | 3 | 4 | 4 | 4 | 4
9 | 3 | 4 | 4 | 4 | 4
$\geq 10$ | 3 | 4 | 4 | 4 | 4

Table 1: $a_{1}(C_{n}\,\square\,P_{m})$ (left) and
$a_{1}^{\prime}(C_{n}\,\square\,P_{m})$ (right)

The values for $a_{1}(C_{n}\,\square\,P_{m})$ and
$a_{1}^{\prime}(C_{n}\,\square\,P_{m})$ are summarized in Table 1.

In the rest of the subsection we prove Theorem 4.2. We begin with the
following lemma that allows us to use the results from the previous
subsection.

###### Lemma 4.3

If $n\geq 3$ and $m\geq 4$, then

$a_{1}(C_{n}\,\square\,P_{m})\leq a_{1}(C_{n}\,\square\,C_{m})\quad{\rm
and}\quad a_{1}^{\prime}(C_{n}\,\square\,P_{m})\leq
a_{1}^{\prime}(C_{n}\,\square\,C_{m})\,.$

Proof. Let $P_{m}$ be obtained from $C_{m}$ after the removal of the edge
$1m$. The clique hypergraph of $C_{n}\,\square\,P_{m}$ is then obtained from
the clique hypergraph of $C_{n}\,\square\,C_{m}$ by removing the cliques
$\\{(i,m),(i,1)\\}$ for every $i\in[n]$.

Suppose now that Alice can win in the $(a,1)$-MCT game on
$C_{n}\,\square\,C_{m}$ and consider one of her optimal strategies. If she
plays according to the same startegy in the $(a,1)$-MCT game on
$C_{n}\,\square\,P_{m}$, Bob cannot claim a clique of $C_{n}\,\square\,C_{m}$
and therefore, he cannot claim a clique in $C_{n}\,\square\,P_{m}$. It follows
that Alice can also win the $(a,1)$-MCT game on $C_{n}\,\square\,P_{m}$. This
argumentation is valid no matter Alice or Bob starts the games and implies
that both $a_{1}(C_{n}\,\square\,P_{m})\leq a_{1}(C_{n}\,\square\,C_{m})$ and
$a_{1}^{\prime}(C_{n}\,\square\,P_{m})\leq
a_{1}^{\prime}(C_{n}\,\square\,C_{m})$ are true. $\square$

###### Proposition 4.4

If $m\geq 2$, then

$\displaystyle a_{1}(C_{3}\,\square\,P_{m})=\begin{cases}2;&2\leq m\leq 5,\\\
3;&{\rm otherwise},\end{cases}$

and

$\displaystyle a^{\prime}_{1}(C_{3}\,\square\,P_{m})=\begin{cases}2;&m=2,\\\
3;&{\rm otherwise}\,.\end{cases}$

Proof. Assume that $m\geq 2$ and consider the $(a,1)$-MCT game on
$C_{3}\,\square\,P_{m}$. We first suppose that Alice starts the game.

#### Case 1:

$2\leq m\leq 5$.
To show that $a_{1}(C_{3}\,\square\,P_{m})\geq 2$, we will provide a winning
strategy for Bob in the Alice-start $(1,1)$-MCT game. Assume that Alice plays
$(i,j)$. Since $m\geq 2$, there exists a vertex $(i^{\prime},j^{\prime})$ with
$i^{\prime}\neq i$ and $j^{\prime}\neq j$. Then Bob replies by playing
$(i^{\prime},j^{\prime})$ and he can win the game within his next two moves.
We infer that $a_{1}(C_{3}\,\square\,P_{m})\geq 2$.

To show that $a_{1}(C_{3}\,\square\,P_{m})\leq 2$, we will provide a winning
strategy for Alice in the Alice-start $(2,1)$-MCT game. We distinguish several
subcases depending on $m$.

Case 1.1: $m=2$.
In $C_{3}\,\square\,P_{2}$, each vertex is incident with exactly two cliques.
Hence Observation 1.5(ii) yields the result.

Case 1.2: $m=3$.
Alice plays $(1,2)$ and $(2,1)$ in her first move. If Bob plays $(i,j)$ in
$(C_{3})^{1}$ or in $(C_{3})^{2}$, then Alice replies by playing all unplayed
neighbors of $(i,j)$ in ${}^{i}(P_{3})$ (and a further arbitrary unplayed
vertex if it is needed). If Bob plays $(i,3)$, where $i\in[3]$, then Alice
plays one vertex in the layer $(C_{3})^{3}$ and $(i,2)$ if it is possible.
Otherwise, Alice can play an arbitrary unplayed vertex. Now, every vertex is
incident to at most two cliques which have not been played by Alice.
Therefore, if Alice plays optimally, Bob cannot claim any clique and Alice
wins the game.

Case 1.3: $m=4$.
By Theorem 4.1 and Lemma 4.3, we have $a_{1}(C_{3}\,\square\,P_{4})\leq
a_{1}(C_{3}\,\square\,C_{4})=2$.

Case 1.4: $m=5$.
Alice plays $(1,4)$ and $(2,2)$ in her first move. Assume that Bob replies
with the vertex $(i,j)$. If $(i,j)\in X=\\{(1,2),(2,4),(3,2),(3,3),(3,4)\\}$,
then Alice chooses two neighbors of $(i,j)$ in the layer ${}^{i}(P_{m})$. When
$(i,j)\notin X$ then, if it is possible, Alice replies by choosing two
neighbors of $(i,j)$, one in $(C_{3})^{j}$ and the other in ${}^{i}(P_{m})$.
Otherwise, Alice can play any unplayed vertex. If she continues playing
according to this strategy, Alice prevents Bob from claiming a clique and she
wins the game.

We conclude that $a_{1}(C_{3}\,\square\,P_{m})\leq 2$ for $2\leq m\leq 5$.

#### Case 2:

$m\geq 6$.
By Lemma 4.3 and Theorem 4.1 we have $a_{1}(C_{3}\,\square\,P_{m})\leq
a_{1}(C_{3}\,\square\,C_{m})=3$.

To prove that $a_{1}(C_{3}\,\square\,P_{m})\geq 3$ we show that Bob can win in
the Alice-start $(2,1)$-MCT game. After Alice plays two vertices in her first
move, there exist three consecutive layers $(C_{3})^{j-1}$, $(C_{3})^{j}$, and
$(C_{3})^{j+1}$, such that at most one vertex from these three layers were
played by Alice and the possibly played vertex is not from $(C_{3})^{j}$. Let
$(1,j-1)$ be the possibly played vertex. No matter whether it was played or
not, Bob replies by $(2,j)$. Then Alice is forced to select $(2,j-1)$ and
$(2,j+1)$. After that, Bob plays $(3,j)$ and will win in his next move.

It remains to consider the Bob-start game on $C_{3}\,\square\,P_{m}$. If
$m=2$, each vertex is contained in two cliques and Observation 1.5(iii)
implies $a^{\prime}_{1}(C_{3}\,\square\,P_{2})\leq 2$. By (1) and the first
part of this proof we have $a_{1}^{\prime}(C_{3}\,\square\,P_{2})\geq
a_{1}(C_{3}\,\square\,P_{2})=2$. Therefore
$a^{\prime}_{1}(C_{3}\,\square\,P_{2})=2$.

Suppose that $m\geq 3$. Then $a^{\prime}_{1}(C_{3}\,\square\,P_{m})\leq 3$ by
Observation 1.5(iii). To see that $a^{\prime}_{1}(C_{3}\,\square\,P_{m})\geq
3$ consider the following strategy of Bob in the Bob-start $(2,1)$-MCT game.
In his first move, he plays $(1,2)$. Then Alice is forced to play $(1,1)$ and
$(1,3)$. Afterwards, Bob replies by the move $(2,2)$ and since Alice cannot
play all of its neighbors, Bob can win in the next turn.

$\square$

Next, we consider the thresholds for $C_{n}\,\square\,P_{2}$ where $n\geq 4$.

###### Proposition 4.5

If $n\geq 4$, then

$\displaystyle a_{1}(C_{n}\,\square\,P_{2})=\begin{cases}2;&n=4,\\\ 3;&n\geq
5.\end{cases}$

Proof. Assume that $n\geq 4$ and consider the Alice-start $(a,1)$-MCT game on
$C_{n}\,\square\,P_{2}$.

#### Case 1:

$n=4$.
Let $X=\\{(1,1),(3,2)\\}$. Then $\Delta((C_{4}\,\square\,P_{2})-X)=2$. By
Theorem 2.1(i), we have that
$a_{1}(C_{4}\,\square\,P_{2})\leq\max\\{\Delta((C_{4}\,\square\,P_{2})-X),|X|\\}=2$.
It suffices to show that Bob has a winning strategy in the $(1,1)$-MCT game.
Assume Alice plays $(i,j)$ in her first move. Then Bob replies by choosing a
vertex $(i^{\prime},j^{\prime})$ such that $i^{\prime}\neq i$ and
$j^{\prime}\neq j$, and he will win the game in his second move. Hence
$a_{1}(C_{4}\,\square\,P_{2})=2$.

#### Case 2:

$n\geq 5$.
Since each vertex is incident with three cliques, Observation 1.5(iii) implies
that $a_{1}(C_{n}\,\square\,P_{2})\leq 3$. It remains to show that
$a_{1}(C_{n}\,\square\,P_{2})\geq 3$ by giving a winning strategy for Bob in
the $(2,1)$-MCT game. Let $A_{1}$ be the set of two vertices played by Alice
in her first move. There exists a vertex $(i,j)$ such that $(i,j)\notin
N[A_{1}]$. Then Bob plays $(i,j)$ in his first move and can win the game in
his next turn. Thus $a_{1}(C_{n}\,\square\,P_{2})=3$. $\square$

For $n\geq 4$, the Cartesian product $C_{n}\,\square\,P_{m}$ is triangle-free
with no isolated vertices. By Theorem 2.1,
$a_{1}^{\prime}(C_{n}\,\square\,P_{m})=\Delta(C_{n}\,\square\,P_{m})$ which
implies the following:

###### Observation 4.6

If $n\geq 4$, then

$\displaystyle a_{1}^{\prime}(C_{n}\,\square\,P_{m})=\begin{cases}3;&m=2,\\\
4;&m\geq 3\,.\end{cases}$

###### Lemma 4.7

Assume that $n\geq 4$ and $m\geq 3$. Then $a_{1}(C_{n}\,\square\,P_{m})=3$ if
and only if $\gamma(C_{n}\,\square\,P_{m-2})\leq 3$.

Proof. Let $G$ be the induced subgraph of $C_{n}\,\square\,P_{m}$ which
remains after the deletion of the vertices from $V((C_{n})^{1})\cup
V((C_{n})^{m})$. Then $G$ is isomorphic to $C_{n}\,\square\,P_{m-2}$. It
suffices to show that $a_{1}(C_{n}\,\square\,P_{m})=3$ if and only if
$\gamma(G)\leq 3$.

$(\Leftarrow)$ Let $X$ be a minimum dominating set of $G$ and assume that
$|X|\leq 3$. We will show that $a_{1}(P_{n}\,\square\,C_{m})=3$. Since each
vertex in $V((C_{n})^{1})\cup V((C_{n})^{m})$ has degree $3$ in
$C_{n}\,\square\,P_{m}$, and $X$ is a dominating set of $G$,
$\Delta((C_{n}\,\square\,P_{m})-X)\leq 3$. By Theorem 2.1(i),
$a_{1}(C_{n}\,\square\,P_{m})\leq\max\\{\Delta((P_{n}\,\square\,P_{n})-X),|X|\\}\leq
3$. To show that $a_{1}(C_{n}\,\square\,P_{m})\geq 3$, we will show that Bob
has a winning strategy in the Alice-start $(2,1)$-MCT game. After Alice plays
two vertices in her first move, there is a vertex $(i,j)$ such that $(i,j)$ is
adjacent to at least three unplayed vertices. Then Bob plays $(i,j)$ and wins
the game in his next move. Therefore $a_{1}(C_{n}\,\square\,P_{m})=3$.

$(\Rightarrow)$ Assume that $a_{1}(C_{n}\,\square\,P_{m})=3$. By Theorem
2.1(i), there exists a set $X$ such that
$\Delta((C_{n}\,\square\,P_{m}))-X)\leq 3$ and $|X|\leq 3$. Then all vertices
of degree $4$ in $C_{n}\,\square\,P_{m}$ belong to
$N_{C_{n}\,\square\,P_{m}}[X]$ which implies that $X$ dominates all vertices
from $V(G)$. If there exists a vertex $(i,j)\in X-V(G)$, then $(i,j)$ is
adjacent to exactly one vertex $(i^{\prime},j^{\prime})$ from $V(G)$ and we
can replace $(i,j)$ with $(i^{\prime},j^{\prime})$ in $X$. By repeating this
process for the remaining vertices of $X$ if necessary, we find a dominating
set of $G$ of order at most $3$. $\square$

In [17], the domination number of $\gamma(C_{n}\,\square\,P_{m})$ was
determined for each pair of parameters with $n\geq 4$ and $2\leq m\leq 7$. It
is well-known that $\gamma(C_{n})=\lceil\frac{n}{3}\rceil$ and that
$\gamma(C_{n}\,\square\,P_{m})>3$ holds whenever $n\geq 4$ and $m\geq 8$. From
these facts we can deduce the following statement:

###### Proposition 4.8

If $n\geq 4$ and $m\geq 1$, then $\gamma(C_{n}\,\square\,P_{m})\leq 3$ if and
only if one of the following conditions holds:

  * $(i)$

$n=4$ and $m\in[3]$;

  * $(ii)$

$n=5$ and $m\in[2]$;

  * $(iii)$

$6\leq n\leq 9$ and $m=1$.

We are now in a position to complete the proof of Theorem 4.2. Since the other
cases have already been covered, it sufficies to consider cylinder graphs
$C_{n}\,\square\,P_{m}$ with $n\geq 4$.

From Lemma 4.7 and Proposition 4.8 we deduce that if $n\geq 4$, then
$a_{1}(C_{n}\,\square\,P_{m})=3$ if and only if either $n=4$ and $3\leq m\leq
5$, or $n=5$ and $3\leq m\leq 4$, or $6\leq n\leq 9$ and $m=3$. It remains to
show that $a_{1}(C_{n}\,\square\,P_{m})=4$ in each of the following cases:

  * $(i)$

$n=4$ and $m\geq 6$,

  * $(ii)$

$n=5$ and $m\geq 5$,

  * $(iii)$

$n\geq 6$ and $m\geq 4$,

  * $(iv)$

$n\geq 10$ and $m=3$.

For these cases, $a_{1}(C_{n}\,\square\,P_{m})\neq 3$ and Theorem 2.1(i)
implies $a_{1}(C_{n}\,\square\,P_{m})>2$. From Observation 1.5(iii) we deduce
$a_{1}(C_{n}\,\square\,P_{m})\leq 4$. Therefore,
$a_{1}(C_{n}\,\square\,P_{m})=4$ holds under the conditions $(i)$-$(iv)$. This
finishes the proof of Theorem 4.2.

###  4.3 Grid graphs

###### Theorem 4.9

If $m\geq n\geq 2$, then

$\displaystyle a_{1}(P_{n}\,\square\,P_{m})=\begin{cases}2;&n=2,2\leq m\leq
5,\text{or\ }\\\ &n=3,m=3,4,\\\ 3;&n=2,m\geq 6,\text{or\ }\\\ &n=3,5\leq m\leq
11,\text{or\ }\\\ &n=4,4\leq m\leq 7,\text{or\ }\\\ &n=m=5,\\\
4;&\text{otherwise}.\end{cases}$

and

$\displaystyle a_{1}^{\prime}(P_{n}\,\square\,P_{m})=\begin{cases}2;&n=m=2,\\\
3;&n=2,m\geq 3,\\\ 4;&m\geq n\geq 3\,.\end{cases}$

Table 2 summarizes the values of $a_{1}(P_{n}\,\square\,P_{m})$.

$n\backslash m$ |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10 |  11 | $\geq 12$
---|---|---|---|---|---|---|---|---|---|---|---
2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3
3 |  | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 4
4 |  |  | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4
5 |  |  |  | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 4
$\geq 6$ |  |  |  |  | 4 | 4 | 4 | 4 | 4 | 4 | 4
Table 2: $a_{1}(P_{n}\,\square\,P_{m})$ for $2\leq n\leq m$

In the rest of the subsection we prove Theorem 4.9. Observe that the Cartesian
product $P_{n}\,\square\,P_{m}$ is triangle-free with no isolated vertices for
all $n,m\geq 2$. By Theorem 2.1(ii),
$a_{1}^{\prime}(P_{n}\,\square\,P_{m})=\Delta(P_{n}\,\square\,P_{m})$ and
thus, we can conclude that

$\displaystyle a_{1}^{\prime}(P_{n}\,\square\,P_{m})=\begin{cases}2;&n=m=2,\\\
3;&n=2,m\geq 3,\\\ 4;&m\geq n\geq 3\,.\end{cases}$

Next, we consider the threshold for the Alice-start game on
$P_{2}\,\square\,P_{m}$ where $m\geq 2$.

###### Proposition 4.10

If $m\geq 2$, then

$\displaystyle a_{1}(P_{2}\,\square\,P_{m})=\begin{cases}2;&2\leq m\leq 5,\\\
3;&m\geq 6\,.\end{cases}$

Proof. Assume that $m\geq 2$ and consider the Alice-start $(a,1)$-MCT game on
$P_{2}\,\square\,P_{m}$.

#### Case 1:

$2\leq m\leq 5$.
To show that $a_{1}(P_{2}\,\square\,P_{m})\geq 2$, we will provide a winning
strategy for Bob in the Alice-start $(1,1)$-MCT game. Assume that Alice plays
$(i,j)$. Then Bob replies by playing a vertex $(i^{\prime},j^{\prime})$ such
that $i^{\prime}\neq i$ and $j^{\prime}\neq j$, and he can win the game with
his next move. Thus $a_{1}(P_{2}\,\square\,P_{m})\geq 2$.

It remains to show that $a_{1}(P_{2}\,\square\,P_{m})\leq 2$. The assertion is
clear for $m=2$. Let $X_{i}=\\{(1,2),(2,i-1)\\}$, $i\in\\{3,4,5\\}$. Then
$\max\\{\Delta((P_{2}\,\square\,P_{i})-X_{i}),|X_{i}|\\}=2$ holds for each
$i\in\\{3,4,5\\}$. Hence Theorem 2.1(i) implies the assertion.

#### Case 2:

$m\geq 6$.
It is straightforward to verify that by deleting any two vertices of
$P_{2}\,\square\,P_{m}$, the maximum degree of the rest of the graph remains
$3$. Hence Theorem 2.1(i) yields $a_{1}(P_{2}\,\square\,P_{m})\geq 3$. On the
other hand, since each vertex in $P_{2}\,\square\,P_{m}$ is incident with at
most three cliques, Observation 1.5(iii) implies
$a_{1}(P_{2}\,\square\,P_{m})\leq 3$. $\square$

###### Lemma 4.11

Assume that $m\geq n\geq 3$. Then $a_{1}(P_{n}\,\square\,P_{m})\leq 3$ holds
if and only if $\gamma(P_{n-2}\,\square\,P_{m-2})\leq 3$.

Proof. The proof proceeds along the same lines as the corresponding inequality
part of the proof of Lemma 4.7. $\square$

Obviously,
$\gamma(P_{n})=\gamma(P_{n}\,\square\,P_{1})=\lceil\frac{n}{3}\rceil$. In [1],
$\gamma(P_{n}\,\square\,P_{m})$ was calculated for $m,n\leq 29$ by using a
dynamic programming algorithm. According to these results we may conclude the
following:

###### Proposition 4.12

If $m\geq n\geq 1$, then $\gamma(P_{n}\,\square\,P_{m})\leq 3$ if and only if
one of the following conditions holds:

  * •

$n=1$ and $1\leq m\leq 9$;

  * •

$n=2$ and $2\leq m\leq 5$;

  * •

$n=m=3$.

###### Lemma 4.13

Assume that $m\geq n\geq 3$. Then $a_{1}(P_{n}\,\square\,P_{m})=2$ if and only
if $n=3$ and $m\in\\{3,4\\}$.

Proof. If $n=3$ and $m\geq 5$, or $m\geq n\geq 4$, then by Theorem 2.1(i) we
get $a_{1}(P_{n}\,\square\,P_{m})>2$. Assume next that $n=3$ and
$m\in\\{3,4\\}$. Let $X=\\{(2,2),(2,3)\\}$. Then
$\Delta((P_{n}\,\square\,P_{m})-X)=2$, so $a_{1}(P_{n}\,\square\,P_{m})\leq 2$
by Theorem 2.1(i). It remains to show that $a_{1}(P_{n}\,\square\,P_{m})\geq
2$ by providing a winning strategy for Bob in the Alice-start $(2,1)$-MCT
game. After Alice plays $(i,j)$ in her first move, it is easy to see that
there is $(i^{\prime},j^{\prime})$ which is $i^{\prime}\neq i$ and
$j^{\prime}\neq j$. Then Bob replies by playing $(i^{\prime},j^{\prime})$ and
wins the game in his next move. Hence $a_{1}(P_{n}\,\square\,P_{m})=2$.
$\square$

For $m\geq n\geq 3$, according to Lemmas 4.11 and 4.13, and to Proposition
4.12, we can conclude that $a_{1}(P_{n}\,\square\,P_{m})=3$ if $m$ and $n$
satisfy one of the following conditions:

  * •

$n=3$ and $5\geq m\geq 11$,

  * •

$n=4$ and $4\geq m\geq 7$,

  * •

$n=m=5$.

To complete the proof of Theorem 4.9, it remains to detect when $m\geq n\geq
3$ and $a_{1}(C_{n}\,\square\,P_{m})>3$ hold. By Observation 1.5(iii) we have
$a_{1}(P_{n}\,\square\,P_{m})\leq 4$, hence in these cases
$a_{1}(P_{n}\,\square\,P_{m})=4$ holds. By Lemma 4.11 and Proposition 4.12,
these are the following cases:

  * •

$n=3$ and $m\geq 12$,

  * •

$n=4$ and $m\geq 8$,

  * •

$n=5$ and $m\geq 6$,

  * •

$m\geq n\geq 6$.

## Acknowledgments

Sandi Klavžar was supported by the Slovenian Research Agency (ARRS) under the
grants P1-0297, J1-2452, and N1-0285. Csilla Bujtás acknowledges the support
of the Slovenian Research Agency (ARRS) under the grant N1-0108.

## References

  * [1] S. Alanko, S. Crevals, A. Isopoussu, P. Ostergard, V. Pettersson, Computing the domination number of grid graphs, Electron. J. Comb. 18 (2011) #P141.
  * [2] C. Berge, Hypergraphs. Combinatorics of Finite Sets, North Holland, 1989.
  * [3] Cs. Bujtás, P. Dokyeesun, Fast winning strategies for Staller in the Maker-Breaker domination game, http://arxiv.org/abs/2206.12812, 2021.
  * [4] C. N. Campos, S. Dantas, C. P. De Mello, Colouring clique-hypergraphs of circulant graphs, Graphs Comb. 29 (2013) 1713–1720.
  * [5] Y. Caro, A. Hansberg, New approach to the $k$-independence number of a graph, Electron. J. Combin. 20 (2013) #P33.
  * [6] M. Chellali, O. Favaron, A. Hansberg, L. Volkmann, $k$-Domination and $k$-independence in graphs: A survey, Graphs Combin. 28 (2012) 1–55.
  * [7] E. Duchêne, V. Gledel, A. Parreau, G. Renault, Maker-Breaker domination game, Discrete Math. 343 (2020) 111955.
  * [8] P. Erdős, J.L. Selfridge, On a combinatorial game, J. Combin. Theory Ser. A 14 (1973) 298–301.
  * [9] C. Glazik, A. Srivastav, A new bound for the Maker-Breaker triangle game, European J. Combin. 104 (2022) 103536.
  * [10] V. Gledel, M. A. Henning, V. Iršič, S. Klavžar, Maker-Breaker total domination game, Discrete Appl. Math. 282 (2020) 96–107.
  * [11] D. Hefetz, M. Krivelevich, M. Stojaković, T. Szabó, Positional Games, Birkhäuser/Springer, Basel, 2014.
  * [12] R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition, CRC Press, Boca Raton, FL, 2011.
  * [13] Z. Liang, J. Wu, E. Shan, List-coloring clique-hypergraphs of $K_{5}$-minor-free graphs strongly, Discrete Math. 343 (2020) 111777.
  * [14] Y. Mao, E. Cheng, Z. Wang, Z. Guo, The $k$-independence number of graph products, Art Discrete Appl. Math. 1 (2018) Paper No. P1.01.
  * [15] W.P. Mendes, S. Dantas, S. Gravier, The $(a,b)$-monochromatic transversal game on biclique-hypergraphs of powers of paths and of powers of cycles, Procedia Comp. Sci. 195 (2021) 181–189.
  * [16] W.P. Mendes, S. Dantas, S. Gravier, R. Marinho, The $(a,b)$-monochromatic transversal game on clique-hypergraphs of powers of cycles, https://hal.archives-ouvertes.fr/hal-03015815, 2021.
  * [17] P. Pavlič, J. Žerovnik, A note on the domination number of the Cartesian products of paths and cycles, Kragujevac J. Math. 37 (2013) 275–285.
  * [18] M. Stojaković, N. Trkulja, Hamiltonian Maker-Breaker games on small graphs, Exp. Math. 30 (2021) 595–604.
  * [19] D.B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001.