# Bounds for the Competition-Independence game on trees

Jan<EMAIL_ADDRESS>Department of Pure Mathematics and Mathematical
Statistics (DPMMS), University of Cambridge, Wilberforce Road, Cambridge, CB3
0WA, United Kingdom Julien<EMAIL_ADDRESS>Department of Pure
Mathematics and Mathematical Statistics (DPMMS), University of Cambridge,
Wilberforce Road, Cambridge, CB3 0WA, United Kingdom

###### Abstract

In this paper we prove that Sweller has a strategy so that the Sweller-Start
Competition-Independence game lasts at least $(5n+3)/13$ moves for every tree.
Moreover, we show that there exist arbitrarily large trees such that the
Sweller-Start Competition-Independence game lasts at most $(5n+26)/12$ moves,
disproving a conjecture by Henning.

##  1 Introduction

_Competition-independence games_ were introduced by Phillips and Slater in
2001 in [11], [12]. With the notation of Goddard and Henning [6], the
competition-independence game on a graph $G$ is played by two players,
Diminisher (D) and Sweller (S). They take turns in constructing a maximal
independent set $M$ of $G$. More precisely, the players alternate turns in
which they choose a vertex that is not adjacent to any of the vertices already
chosen by any of the 2 players until there is no such vertex. Upon completion
of the game, the resulting set of chosen vertices is indeed a maximal
independent set of $G$, and in particular a dominating set of $G$. The goal of
Diminisher is to make the final set $M$ as small as possible and for Sweller
to make the final set $M$ as large as possible.

Even though the competition-independence games had been introduced before
2010, when the domination games were first studied, a competition-independence
game is a member of the family of the domination games. Those have received
much attention, see e.g. [2, 8, 10, 5, 15, 14, 9, 13, 4, 1], and [3] for a
general survey.

For a graph G, let $I_{s}(G)$ denote the length of the competition-
independence game if Sweller moves first and both players play optimally and
let $I_{d}(G)$ denote the length of the competition-independence game if
Diminisher moves first and both players play optimally. These numbers are
called the competition-independence numbers. Phillips and Slater noticed [12]
that for a path on $n$ vertices we have $I_{s}(P_{n})=\frac{3}{7}n+\theta(1)$
and wondered if this was the worst-case for Sweller among all trees. This
prompted Henning [7] to pose the following conjecture.

######  Conjecture 1.1.

Let $T$ be a tree of order $n$. Then $I_{s}(T)\geq\frac{3}{7}n$.

In the first part of this paper, we disprove 1.1 by showing the following
result.

######  Theorem 1.2.

There exist trees $T$ of size arbitrarily large satisfying
$I_{s}(T)\leq\frac{5n+26}{12}$.

Goddard and Henning [6] proved that, for any tree $T$ on $n$ vertices and
maximum degree at most 3, we have $I_{s}(T)\geq 3n/8$. In the second part of
our paper, we prove that a larger lower bound holds for every tree.

######  Theorem 1.3.

Let $T$ be a tree of order $n$. Then $I_{s}(T)\geq\frac{5n+3}{13}$.

##  2 The upper bound

This section is devoted to proving the following result, which indeed
immediately implies Theorem 1.2.

######  Theorem 2.1.

For every $k\in\mathbb{N}$, there exists a tree $T_{k}$ on $n=2\cdot(3k+1)$
vertices such that $I_{s}(T_{k})\leq\frac{5}{12}n+\frac{13}{6}$.

###### Proof.

Let $S_{k}$ be the graph formed by $k$ paths on $3$ vertices, each connected
by one of its endpoints to a central vertex. The tree $T_{k}$ is formed by
joining two copies of $S_{k}$ by their central vertices.

Figure 1: The tree $T_{k}$.

We describe here a strategy for Diminisher such that the Sweller-Start
competition-independence game on $T_{k}$ finishes after at most $3+5k/2$
moves. If Sweller plays for its first move one of the central vertices, then
Diminisher plays any legal move for its first move. Otherwise, one of the
central vertices is a legal move, which Diminisher plays for its first move.
Let $S^{1}_{k}$ be the copy of $S_{k}$ where the central vertex has been
played and $S^{2}_{k}$ be the copy of $S_{k}$ where the central vertex has not
been played. For the next moves, we instruct Diminisher to play the middle
vertex on each of the paths of $S^{2}_{k}$ where no player has played yet,
thus making sure only one move is played on these paths throughout the whole
game. It is clear that Diminisher is able to play at least
$\lfloor\frac{k-1}{2}\rfloor$ of those moves. On the remaining paths in
$S^{2}_{k}$ at most two moves will be played throughout the game, and on each
path of $S^{1}_{k}$ exactly one move will be played throughout the game.

In total, we have $I_{s}(T_{k})\leq
2+\lfloor\frac{k-1}{2}\rfloor+2\cdot\lceil\frac{k+1}{2}\rceil+k\leq
3+\frac{5}{2}k=\frac{5}{12}n+\frac{13}{6}$. ∎

##  3 The lower bound

We actually prove a slightly stronger result, which obviously implies Theorem
1.3.

######  Theorem 3.1.

Let $F$ be a forest of order $n$ with $C$ connected components. Then
$I_{s}(F)\geq\frac{5n+3C}{13}$.

The rest of this section is devoted to proving Theorem 3.1.

###  3.1 The strategy and notation

The competition-independence game can be rephrased as follows. Starting with a
graph $G$, the players take turns, alternatively removing vertices together
with their neighbourhoods. The game ends when the resulting graph is empty.
Diminisher’s goal is to make the game as short as possible, whereas Sweller’s
goal is to make it last as long as possible.

Considering global properties of graphs, a candidate for a heuristically good
move for Sweller

  * •

removes only few vertices, and also, with the aim to make future moves remove
fewer vertices,

  * •

removes many edges (so that neighbourhoods get smaller), and

  * •

creates many isolated vertices (as they will need to be played at some point,
not removing any more vertices).

The following paragraphs are devoted to introducing Sweller’s strategy for
Sweller-start competition game on a forest $F$ on $C$ components, together
with notation we shall use. Let $K(G)$ stand for the number of isolated
vertices in a graph $G$. With the convention of $F_{D}^{0}=F$, let $F_{i}^{D}$
be the forest after Diminisher’s $i$-th move. For any $u\in V(F_{i-1}^{D})$,
we set:

  * •

$v_{i}^{S}(u)=|N[u]|$, that is, the number of vertices that get removed if
Sweller chooses $u$ for its move,

  * •

$e_{i}^{S}(u)=|E(F_{i-1}^{D})|-|E(F_{i-1}^{D}-N[u])|$, that is, the number of
edges that get removed if Sweller chooses $u$ for its move, and

  * •

$k_{i}^{S}(u)=K(F_{i-1}^{D}-N[u])-K(F_{i-1}^{D})$, that is, the difference
between the number of isolated vertices in the resulting forest if Sweller
chooses $u$ and in $F_{i-1}^{D}$.

We instruct Sweller to follow a simple greedy strategy:

######  Strategy 3.2.

Sweller picks any vertex $w$ that minimizes the function
$m_{i}^{S}:V(F_{i-1}^{D})\rightarrow\mathbb{R}$, with
$m_{i}^{S}(u)=(1-\beta)k_{i}^{S}(u)+v_{i}^{S}(u)-\alpha e_{i}^{S}(u)$, where
$\alpha=3/8$ and $\beta=13/8$.

Suppose Sweller follows this greedy strategy and consider any sequence of
Diminisher’s replies. Let $N$ be the number of moves the game lasts. We will
ultimately show $N\geq(5n+3C)/13$. Note that if $N$ is even, Diminisher plays
the last move, whereas if $N$ is odd, the last move is played by Sweller. We
set $r=\lfloor\frac{N}{2}\rfloor$, the number of moves played by Diminisher.

Let $w_{i}^{S}$ be the vertex Sweller chooses for its $i$-th move and let
$F_{i}^{S}$ be the forest after Sweller’s $i$-th move, that is,
$F_{i}^{S}=F_{i-1}^{D}-N[w_{i}^{S}]$. Furthermore, let $w_{i}^{D}$ be the
$i$-th move of Diminisher, then $F_{i}^{D}=F_{i}^{S}-N[w_{i}^{D}]$.
Analogously to $v_{i}^{S},e_{i}^{S},k_{i}^{S}$ and $m_{i}^{S}$, for any vertex
$u\in V(F_{i}^{S})$ we define:

  * •

$v_{i}^{D}(u)=|N[u]|$,

  * •

$e_{i}^{D}(u)=|E(F_{i}^{S})|-|E(F_{i}^{S}-N[u])|$,

  * •

$k_{i}^{D}(u)=K(F_{i}^{S}-N[u])-K(F_{i}^{S})$,

and $m_{i}^{D}:V(F_{i}^{S})\rightarrow\mathbb{R}$ as
$m_{i}^{D}(u)=(1-\beta)k_{i}^{D}(u)+v_{i}^{D}(u)-\alpha e_{i}^{D}(u)$.

It will be convenient for us to consider changes to the forest after both
players make their move. In accordance with this, for all $i\leq r$ we set:

  * •

$v_{i}=|V(F_{D}^{i-1})|-|V(F_{D}^{i})|$, that is, the number of vertices that
get removed by both players during their $i$-th moves,

  * •

$e_{i}=|E(F_{D}^{i-1})|-|E(F_{D}^{i})|$, that is, the number of edges that get
removed by both players during their $i$-th moves, and

  * •

$k_{i}=|K(F_{D}^{i})|-|K(F_{D}^{i-1})|$, that is, the increment in number of
isolated vertices over the $i$-th moves of both players.

Finally, we set $m_{i}=(1-\beta)k_{i}+v_{i}-\alpha
e_{i}=m_{i}^{S}(w_{i}^{S})+m_{i}^{D}(w_{i}^{D})$.

###  3.2 Key lemma

This subsection is devoted to proving the following lemma, which gives a bound
on all $m_{i}$. The proof of Theorem 3.1 straightforwardly follows, as we show
in the next subsection.

Recall that $r=\lfloor\frac{N}{2}\rfloor$ is the number of moves played by
Diminisher.

######  Lemma 3.3.

For every $i\leq r$, we have

$2\beta\geq(1-\beta)k_{i}+v_{i}-\alpha e_{i}.$

Moreover, if $N$ is odd, we have

$\beta\geq(1-\beta)k_{r+1}^{S}(w_{r+1}^{S})+v_{r+1}^{S}(w_{r+1}^{S})-\alpha
e_{r+1}^{S}(w_{r+1}^{S}).$

To prove Lemma 3.3, we shall show that given Diminisher’s $i$-th move
$w_{i}^{D}$ Sweller could have picked a vertex $\hat{w}_{i}^{S}$ "near"
$w_{i}^{D}$ for its $i$-th move so that $2\beta\geq
m_{i}^{S}(\hat{w}_{i}^{S})+m_{i}^{D}(w_{i}^{D})$. As
$m_{i}^{S}(\hat{w}_{i}^{S})\geq m_{i}^{S}(w_{i}^{S})$, the lemma follows.

We shall make a distinction of cases based on $v_{i}^{D}(w_{i}^{D})$ and
$e_{i}^{D}(w_{i}^{D})$. Let $y_{1},\ldots,y_{l}$ be the neighbours of
$w_{i}^{D}$ in $F_{i}^{S}$, so that $v_{i}^{D}(w_{i}^{D})=1+l$. Let $p$ stand
for the number of edges in $F_{i}^{S}-w_{i}^{D}$ with at least one endpoint
among $\\{y_{1},\ldots,y_{l}\\}$, then $e_{i}^{D}(w_{i}^{D})=l+p$.

######  Lemma 3.4.

Let $i\leq r$ and suppose $v_{i}^{D}(w_{i}^{D})=1+l$ and
$e_{i}^{D}(w_{i}^{D})=l+p$ for some $l\geq 1$. Then there is
$\hat{w}_{i}^{S}\in V(F_{i-1}^{D})$ such that

  * •

either $v_{i}^{S}(\hat{w}_{i}^{S})=q+2$, $e_{i}^{S}(\hat{w}_{i}^{S})\geq q+l$
and $k_{i}^{S}(\hat{w}_{i}^{S})\geq l-p-2$ for some
$q\leq\lfloor\frac{p}{l}\rfloor$,

  * •

or $v_{i}^{S}(\hat{w}_{i}^{S})=q+3$, $e_{i}^{S}(\hat{w}_{i}^{S})\geq q+l+2$
and $k_{i}^{S}(\hat{w}_{i}^{S})\geq l-p-1$ for some
$q\leq\lfloor\frac{p}{l}\rfloor$.

###### Proof.

Let $y_{1},\dots,y_{l}$ be the neighbours of $w_{i}^{D}$ in $F_{i}^{S}$. Then
by pigeonhole principle and the fact that $F_{i}^{S}$ is acyclic, there exists
a vertex $y_{j}$ that is adjacent in $F_{i}^{S}$ to exactly $1+q$ of the edges
removed during Diminisher’s $i$-th move for some
$q\leq\lfloor\frac{p}{l}\rfloor$. Let $y_{j}w_{i}^{D}$, $y_{j}a_{1}$, $\dots$,
$y_{j}a_{q}$ be those edges. First, note that $y_{j}$ has at most $2+q$
neighbours in $F_{i-1}^{D}$, as otherwise $w_{i}^{S}$ would have at least $2$
common neighbours with $y_{j}$ in $F_{i-1}^{D}$, which is impossible since
$F_{i-1}^{D}$ is acyclic.

If $y_{j}$ has exactly $1+q$ neighbours in $F_{i-1}^{D}$, then
$\hat{w}_{i}^{S}=y_{j}$ was a possible Sweller’s $i$-th move removing $q+2$
vertices $y_{j}$, $w_{i}^{D}$, $a_{1}$, $\dots$, $a_{q}$ and at least the
$q+l$ edges $y_{j}a_{1}$, $\dots$, $y_{j}a_{q}$, $y_{1}w_{i}^{D}$, $\dots$,
$y_{l}w_{i}^{D}$ and making at least $l-p-2$ vertices isolated, as at least
$l-p-2$ of the $y_{l}$’s with $l\neq j$ each have $w_{i}^{D}$ as their only
neighbour in $F_{i-1}^{D}$, leading to the first outcome of the lemma.

If $y_{j}$ has exactly $2+q$ neighbours in $F_{i-1}^{D}$, then $w_{i}^{S}$ has
exactly one common neighbour with $y_{j}$ in $F_{i-1}^{D}$, say $x$. Then
$\hat{w}_{i}^{S}=y_{j}$ was a possible Sweller’s $i$-th move removing the
$q+3$ vertices $w_{i}^{S}$, $y_{j}$, $x$, $a_{1}$, $\dots$, $a_{q}$ and at
least the $q+l+2$ edges $y_{j}x$, $w_{i}^{S}x$, $y_{j}a_{1}$, $\dots$,
$y_{j}a_{q}$, $y_{1}w_{i}^{D}$, $\dots$, $y_{l}w_{i}^{D}$ and making at least
$l-p-1$ vertices isolated, as at least $l-p-1$ of the $y_{l}$’s with $l\neq j$
each have $w_{i}^{D}$ as their only neighbour in $F_{i-1}^{D}$, leading to the
second outcome of the lemma. ∎

######  Lemma 3.5.

Let $i\leq r$ and suppose $v_{i}^{D}(w_{i}^{D})=1+l$ and
$e_{i}^{D}(w_{i}^{D})=l+p$ for some $l\geq 1$. Then there is
$\hat{w}_{i}^{S}\in V(F_{i-1}^{D})$ such that

  * •

either $v_{i}^{S}(\hat{w}_{i}^{S})=l+1$ and $e_{i}^{S}(\hat{w}_{i}^{S})\geq
p+l$,

  * •

or $v_{i}^{S}(\hat{w}_{i}^{S})=l+2$ and $e_{i}^{S}(\hat{w}_{i}^{S})\geq
p+l+2$.

###### Proof.

Set $\hat{w}_{i}^{S}=w_{i}^{D}$. Then, in the same spirit as the proof of the
previous lemma, distinguishing upon $w_{i}^{D}$ having $1+l$ or $2+l$
neighbours in $F_{i-1}^{D}$, we get each of the two outcomes claimed in the
lemma. ∎

The next lemma is a refinement of the two previous lemmas for small values of
$l$ and $p$.

######  Lemma 3.6.

Suppose $v_{i}^{D}(w_{i}^{D})=1+l$ and $e_{i}^{D}(w_{i}^{D})=l+p$.

  1. 1.

If $l=2$ and $p=0$, then there is $\hat{w}_{i}^{S}\in V(F_{i-1}^{D})$ such
that

     * •

either $v_{i}^{S}(\hat{w}_{i}^{S})=2$, $e_{i}^{S}(\hat{w}_{i}^{S})\geq 2$ and
$k_{i}^{S}(\hat{w}_{i}^{S})\geq 1$,

     * •

or $v_{i}^{S}(\hat{w}_{i}^{S})=3$, $e_{i}^{S}(\hat{w}_{i}^{S})\geq 4$ and
$k_{i}^{S}(\hat{w}_{i}^{S})\geq 1$.

  2. 2.

If $l=3$ and $p=0$, then there is $\hat{w}_{i}^{S}\in V(F_{i-1}^{D})$ such
that $v_{i}^{S}(\hat{w}_{i}^{S})=2$, $e_{i}^{S}(\hat{w}_{i}^{S})\geq 3$ and
$k_{i}^{S}(\hat{w}_{i}^{S})\geq 1$.

  3. 3.

If $l=3$ and $p=1$, then there is $\hat{w}_{i}^{S}\in V(F_{i-1}^{D})$ such
that

     * •

either $v_{i}^{S}(\hat{w}_{i}^{S})=2$, $e_{i}^{S}(\hat{w}_{i}^{S})\geq 3$ and
$k_{i}^{S}(\hat{w}_{i}^{S})\geq 1$,

     * •

or $v_{i}^{S}(\hat{w}_{i}^{S})=3$, $e_{i}^{S}(\hat{w}_{i}^{S})\geq 5$ and
$k_{i}^{S}(\hat{w}_{i}^{S})\geq 1$.

  4. 4.

If $l=2$ and $p=1$ or $3\leq l=p\leq 4$, then there is $\hat{w}_{i}^{S}\in
V(F_{i-1}^{D})$ such that $v_{i}^{S}(\hat{w}_{i}^{S})=2$ and
$e_{i}^{S}(\hat{w}_{i}^{S})\geq 2$.

  5. 5.

If $l=1$ and $p=0$, then there is $\hat{w}_{i}^{S}\in V(F_{i-1}^{D})$ such
that $v_{i}^{S}(\hat{w}_{i}^{S})=2$ and $e_{i}^{S}(\hat{w}_{i}^{S})\geq 1$.

  6. 6.

If $l=0$ and $p=0$, then there is $\hat{w}_{i}^{S}\in V(F_{i-1}^{D})$ such
that

     * •

either $v_{i}^{S}(\hat{w}_{i}^{S})=2$ and $e_{i}^{S}(\hat{w}_{i}^{S})\geq 1$,

     * •

or $v_{i}^{S}(\hat{w}_{i}^{S})=1$ and $k_{i}^{S}(\hat{w}_{i}^{S})=-1$.

###### Proof.

In each case, let $y_{1},\dots,y_{l}$ be the neighbours of $w_{i}^{D}$ in
$F_{i}^{S}$.

  1. 1.

In this case, observe that in the forest $F_{i-1}^{D}$, we must be in one of
those two subcases (up to a permutation of the vertices $y_{1}$ and $y_{2}$):
either both $y_{1}$ and $y_{2}$ have exactly one neighbour or $y_{1}$ has
exactly one neighbour $w_{i}^{D}$ and $y_{2}$ has exactly two neighbours
$w_{i}^{D}$ and $x$, such that $x$ is a neighbour of $w_{i}^{S}$.

In the first subcase, $\hat{w}_{i}^{S}=y_{2}$ was a possible Sweller’s $i$-th
move removing $2$ vertices $y_{2}$ and $w_{i}^{D}$, removing at least the $2$
edges $y_{2}w_{i}^{D}$ and $y_{1}w_{i}^{D}$ and making at least the vertex
$y_{1}$ isolated.

In the second subcase, $\hat{w}_{i}^{S}=y_{2}$ was a possible Sweller’s $i$-th
move removing $3$ vertices $x$, $y_{2}$ and $w_{i}^{D}$, removing at least $4$
edges $xw_{i}^{S}$, $xy_{2}$, $y_{2}w_{i}^{D}$ and $y_{1}w_{i}^{D}$ and making
at least the vertex $y_{1}$ isolated.

  2. 2.

In this case, observe that in $F_{i-1}^{D}$, at most one of $y_{1}$, $y_{2}$
and $y_{3}$ has another neighbour, say $y_{3}$. Then $\hat{w}_{i}^{S}=y_{1}$
was a possible Sweller’s $i$-th move removing $2$ vertices $y_{1}$ and
$w_{i}^{D}$, removing at least $3$ edges $y_{1}w_{i}^{D}$, $y_{2}w_{i}^{D}$
and $y_{3}w_{i}^{D}$ and making at least the vertex $y_{2}$ isolated.

  3. 3.

In this case, observe that in $F_{i-1}^{D}$, at least one of $y_{1}$, $y_{2}$
and $y_{3}$ has exactly one neighbour, say $y_{1}$. Then the vertex $y_{1}$
was a possible Sweller’s $i$-th move removing $2$ vertices $y_{1}$ and
$w_{i}^{D}$ and removing at least $3$ edges $w_{i}^{D}y_{1}$, $w_{i}^{D}y_{2}$
and $w_{i}^{D}y_{3}$. If $k_{i}^{S}(y_{1})\geq 1$, set
$\hat{w}_{i}^{S}=y_{1}$.

Now, suppose $k_{i}^{S}(y_{1})=0$. Then each of $y_{2},y_{3}$ has exactly one
neighbour other than $w_{i}^{D}$ in $F_{i-1}^{D}$, and consequently exactly
one of $y_{2},y_{3}$, say $y_{3}$, has a common neighbour $x$ with $w_{i}^{S}$
in $F_{i-1}^{D}$. Then $\hat{w}_{i}^{S}=y_{3}$ was a possible Sweller’s $i$-th
move, removing $3$ vertices $w_{i}^{D},y_{3},x$, removing at least $5$ edges
$w_{i}^{D}y_{1},w_{i}^{D}y_{2},w_{i}^{D}y_{3},y_{3}x$ and $xw_{i}^{S}$ and
making at least the vertex $y_{1}$ isolated.

  4. 4.

In this case, observe that there exists a leaf $u$ in $F_{i-1}^{D}$ such that
its neighbour has degree at least $2$. Then $\hat{w}_{i}^{S}=u$ was a possible
Sweller’s $i$-th move removing $2$ vertices and at least $2$ edges.

  5. 5.

In this case, let $u$ be a leaf of $F_{i-1}^{D}$. Then $\hat{w}_{i}^{S}=u$ was
a possible Sweller’s $i$-th move removing $2$ vertices and at least $1$ edge.

  6. 6.

In this case, $F_{i-1}^{D}$ contains either a leaf $u$ or an isolated vertex
$u^{\prime}$. Then it is straightforward to check that $\hat{w}_{i}^{S}=u$
leads to the first outcome and $\hat{w}_{i}^{S}=u^{\prime}$ leads to the
second.

∎

All that remains to prove the key lemma is a matter of casework and simple
calculations, the details of which can be found in Appendix A.

###  3.3 Bounding the number of moves

We now prove Theorem 1.3 using Lemma 3.3. Recall that $N$ is the total number
of moves played by both players. Since the number of vertices removed
throughout the game is exactly the number $n$ of vertices in $F$, we have

$\displaystyle n=\sum_{i=1}^{\lceil
N/2\rceil}v_{i}^{S}(w_{i}^{S})+\sum_{i=1}^{\lfloor
N/2\rfloor}v_{i}^{D}(w_{i}^{D})=\sum_{i=1}^{r}v_{i}+\mathbbm{1}_{\\{2\nmid
N\\}}\cdot v_{r+1}^{S}(w_{r+1}^{S}).$ (1)

Similarly, the number of edges removed throughout the game is exactly the
number of edges in $F$, hence we have

$\displaystyle n-C=\sum_{i=1}^{\lceil
N/2\rceil}e_{i}^{S}(w_{i}^{S})+\sum_{i=1}^{\lfloor
N/2\rfloor}e_{i}^{D}(w_{i}^{D})=\sum_{i=1}^{r}e_{i}+\mathbbm{1}_{\\{2\nmid
N\\}}\cdot e_{r+1}^{S}(w_{r+1}^{S}).$ (2)

Moreover, as $k_{i}$ is the increment of the number of isolated vertices, and
that there are no isolated vertices once the game ends, we have

$\displaystyle 0\geq\sum_{i=1}^{\lceil
N/2\rceil}k_{i}^{S}(w_{i}^{S})+\sum_{i=1}^{\lfloor
N/2\rfloor}k_{i}^{D}(w_{i}^{D})=\sum_{i=1}^{r}k_{i}+\mathbbm{1}_{\\{2\nmid
N\\}}\cdot k_{r+1}^{S}(w_{r+1}^{S}).$ (3)

Using Lemma 3.3 and then plugging (1), (2) and (3) gives

$\displaystyle N$ $\displaystyle=\sum_{i=1}^{\lfloor
N/2\rfloor}2+\mathbbm{1}_{\\{2\nmid N\\}}$
$\displaystyle\geq\frac{1}{\beta}(\sum_{i=1}^{r}(1-\beta)k_{i}+v_{i}-\alpha
e_{i})+\frac{1}{\beta}\mathbbm{1}_{\\{2\nmid
N\\}}\cdot((1-\beta)k_{r+1}^{S}(w_{i}^{S})+v_{r+1}^{S}(w_{i}^{S})-\alpha
e_{r+1}^{S}(w_{i}^{S}))$
$\displaystyle\geq\frac{1-\alpha}{\beta}n+\frac{\alpha C}{\beta},$

hence, $N\geq\frac{5n+3C}{13}$ as wanted.∎

##  4 Concluding remarks and further directions

The following question remains unsolved.

######  Question 4.1.

What is the value of $c=\inf\\{\dfrac{I_{s}(T)}{|V(T)|}:\text{T is a
tree}\\}$?

In this paper, we showed that we have $5/13\leq c\leq 5/12$. The values of the
constants $\alpha$ and $\beta$ have been optimised but the authors believe
that with the same method and a more careful case analysis, it is likely that
one can improve Theorem 1.3 to a lower bound $c^{\prime}n$ for some
$c^{\prime}>5/13$. However, it does not seem that the technique developped
here could lead to anything better than a lower bound of $2n/5$ for the
following reason. With the notations from the previous section, if
Diminisher’s first move has $l=p=n/5$, then the best we can ensure with the
reasoning we had above is that Sweller’s previous move removed constantly many
vertices and roughly $n/5$ edges from the graph. Then our technique cannot
rule out that the resulting graph is now roughly a disjoint union of $2n/5$
$K_{2}$’s, and consequently that the game will last roughly $2n/5$ more moves.
Hence, if it turns out that $c>2/5$ it seems necessary that a proof of such a
lower bound will require analysis of the general structure of the graph and
not just of the local structure around Diminisher’s moves.

Note that one can ask 4.1 for forests instead of trees as it is not clear
whether the two problems have the same answer.

The authors would also like to point out that the following conjecture posed
by Goddard and Henning [6] is yet to be settled.

######  Conjecture 4.2.

Let $T$ be a tree of order $n\geq 2$, then $I_{d}(T)\leq\frac{3}{4}n$.

## Acknowledgement

The authors would like to thank their PhD supervisor Béla Bollobás for his
valuable comments.

## References

  * Alon et al. [2002] N. Alon, J. Balogh, B. Bollobás, and T. Szabó.  Game domination number.  _Discrete mathematics_ , 256(1-2):23–33, 2002\.
  * Brešar et al. [2010] B. Brešar, S. Klavžar, and D. F. Rall.  Domination game and an imagination strategy.  _SIAM Journal on Discrete Mathematics_ , 24(3):979–991, 2010.
  * Brešar et al. [2021] B. Brešar, M. A. Henning, S. Klavžar, and D. F. Rall.  _Domination games played on graphs_.  Springer, 2021.
  * Bujtás et al. [2016] C. Bujtás, M. A. Henning, and Z. Tuza.  Transversal game on hypergraphs and the 34-conjecture on the total domination game.  _SIAM Journal on Discrete Mathematics_ , 30(3):1830–1847, 2016.
  * Bujtás et al. [2022] C. Bujtás, V. Iršič, and S. Klavžar.  1/2-conjectures on the domination game and claw-free graphs.  _European Journal of Combinatorics_ , 101:103467, 2022.
  * Goddard and Henning [2018] W. Goddard and M. A. Henning.  The competition-independence game in trees.  _J. Combin. Math. Combin. Comput_ , 104:161–170, 2018.
  * Henning [2018] M. A. Henning.  My favorite domination game conjectures.  In _Graph Theory_ , pages 135–148. Springer, 2018.
  * Henning and Kinnersley [2016] M. A. Henning and W. B. Kinnersley.  Domination game: A proof of the 3/5-conjecture for graphs with minimum degree at least two.  _SIAM Journal on Discrete Mathematics_ , 30(1):20–35, 2016.
  * Henning et al. [2017] M. A. Henning, S. Klavžar, and D. F. Rall.  The 4/5 upper bound on the game total domination number.  _Combinatorica_ , 37(2):223–251, 2017.
  * Kinnersley et al. [2013] W. B. Kinnersley, D. B. West, and R. Zamani.  Extremal problems for game domination number.  _SIAM Journal on Discrete Mathematics_ , 27(4):2090–2107, 2013.
  * Phillips and Slater [2001] J. B. Phillips and P. J. Slater.  An introduction to graph competition independence and enclaveless parameters.  _Graph Theory Notes NY_ , 41:37–41, 2001.
  * Phillips and Slater [2002] J. B. Phillips and P. J. Slater.  Graph competition independence and enclaveless parameters.  _Congressus Numerantium_ , pages 79–100, 2002.
  * Portier and Versteegen [2022] J. Portier and L. Versteegen.  A proof of the 3/4 conjecture for the total domination game.  _arXiv preprint arXiv:2211.16432_ , 2022.
  * Portier and Versteegen [2023] J. Portier and L. Versteegen.  Progress towards the 1/2-conjecture for the domination game.  _arXiv preprint arXiv:2301.05202_ , 2023.
  * Versteegen [2022] L. Versteegen.  A proof of the 3/5-conjecture in the domination game.  _arXiv preprint arXiv:2212.04527_ , 2022.

##  Appendix A Proof of Lemma 3.3

This result will mainly follow from Lemma 3.4 and Lemma 3.5, except for a few
small cases that we will treat using Lemma 3.6.

First, we show $2\beta\geq(1-\beta)k_{i}+v_{i}-\alpha e_{i}$ for all $i\leq
r$. Suppose $v_{i}^{D}(w_{i}^{D})=1+l$ and $e_{i}^{D}(w_{i}^{D})=l+p$. We
split all possible pairs of $(l,p)$ as follows (see Figure 2 for
illustration):

Figure 2: An illustration of how cases (I.)–(XIII.) cover all pairs $(l,p)$.

  1. (I.)

First, suppose $p\geq l+1$ and $l\geq 4$. By Lemma 3.4, we have:

     * •

either $(1-\beta)k_{i}+v_{i}-\alpha e_{i}\leq(q+2+l+1)-\frac{3}{8}(q+l+l+p),$

     * •

or $(1-\beta)k_{i}+v_{i}-\alpha e_{i}\leq(q+3+l+1)-\frac{3}{8}(q+l+2+l+p).$

Note that
$(q+2+l+1)-\frac{3}{8}(q+l+l+p)\leq(q+3+l+1)-\frac{3}{8}(q+l+2+l+p)$, so it
suffices to prove that $(q+3+l+1)-\frac{3}{8}(q+l+2+l+p)\leq
2\beta=\frac{13}{4}$, which is indeed true:

$\displaystyle\frac{13}{4}-((q+3+l+1)-\frac{3}{8}(q+l+2+l+p))$
$\displaystyle=\frac{3}{8}p-\frac{1}{4}l-\frac{5}{8}q$
$\displaystyle\geq\frac{3}{8}p-\frac{1}{4}l-\frac{5p}{8l}.$

Using the assumptions $p\geq l+1$ and $l\geq 4$, we get:

$\displaystyle\frac{3}{8}p-\frac{1}{4}l-\frac{5p}{8l}$
$\displaystyle\geq(l+1)\frac{3l-5}{8l}-\frac{1}{4}l$
$\displaystyle=\frac{l^{2}-2l-5}{8l}$ $\displaystyle\geq 0.$

  2. (II.)

Suppose $p=l$ and $l\geq 5$. This is very similar to the previous case; it
suffices to prove that $(q+3+l+1)-\frac{3}{8}(q+l+2+l+p)\leq
2\beta=\frac{13}{4}$, which is indeed true:

$\displaystyle\frac{13}{4}-((q+3+l+1)-\frac{3}{8}(q+l+2+l+p))$
$\displaystyle=\frac{3}{8}p-\frac{1}{4}l-\frac{5}{8}q$
$\displaystyle\geq\frac{3}{8}p-\frac{1}{4}l-\frac{5}{8}$
$\displaystyle=\frac{l-5}{8}$ $\displaystyle\geq 0.$

  3. (III.)

Suppose $p=l-1$ and $l\geq 3$. Note that $q=0$, and that as in the previous
case, it suffices to prove that $(q+3+l+1)-\frac{3}{8}(q+l+2+l+p)\leq
2\beta=\frac{13}{4}$, which is indeed true:

$\displaystyle\frac{13}{4}-((q+3+l+1)-\frac{3}{8}(q+l+2+l+p))$
$\displaystyle=\frac{3}{8}p-\frac{1}{4}l$ $\displaystyle=\frac{l-3}{8}$
$\displaystyle\geq 0.$

  4. (IV.)

Suppose $p\leq l-2$ and $l\geq 4$. Note that $q=0$ and by Lemma 3.4, we have:

     * •

either $(1-\beta)k_{i}+v_{i}-\alpha
e_{i}\leq-\frac{5}{8}(l-2-p)+(2+l+1)-\frac{3}{8}(l+l+p),$

     * •

or $(1-\beta)k_{i}+v_{i}-\alpha
e_{i}\leq-\frac{5}{8}(l-1-p)+(3+l+1)-\frac{3}{8}(l+2+l+p).$

Note that
$-\frac{5}{8}(l-2-p)+(2+l+1)-\frac{3}{8}(l+l+p)\geq-\frac{5}{8}(l-1-p)+(3+l+1)-\frac{3}{8}(l+2+l+p)$
so it suffices to prove that
$-\frac{5}{8}(l-2-p)+(2+l+1)-\frac{3}{8}(l+l+p)\leq 2\beta=\frac{13}{4}$,
which is indeed true:

$\displaystyle\frac{13}{4}-(-\frac{5}{8}(l-2-p)+(2+l+1)-\frac{3}{8}(l+l+p))$
$\displaystyle=-1-\frac{1}{4}p+\frac{3}{8}l$
$\displaystyle\geq-1-\frac{1}{4}(l-2)+\frac{3}{8}l$
$\displaystyle=\frac{l-4}{8}$ $\displaystyle\geq 0.$

  5. (V.)

Suppose $5l-3p\leq 4$ and $l\geq 1$, then by Lemma 3.5, we have:

     * •

either $(1-\beta)k_{i}+v_{i}-\alpha e_{i}\leq(2+2l)-\frac{3}{8}(2l+2p),$

     * •

or $(1-\beta)k_{i}+v_{i}-\alpha e_{i}\leq(3+2l)-\frac{3}{8}(2l+2p+2).$

Note that $(3+2l)-\frac{3}{8}(2l+2p+2)\geq(2+2l)-\frac{3}{8}(2l+2p)$ so it
suffices to prove that $(3+2l)-\frac{3}{8}(2l+2p+2)\leq 2\beta=\frac{13}{4}$,
which is indeed true:

$\displaystyle\frac{13}{4}-((3+2l)-\frac{3}{8}(2l+2p+2))=\frac{4-5l+3p}{4}\geq
0.$

  6. (VI.)

If $l=2$ and $p=0$, then by Lemma 3.6, we have either
$(1-\beta)k_{i}+v_{i}-\alpha e_{i}\leq(1-\beta)+5-4\alpha=\frac{23}{8}\leq
2\beta$ or $(1-\beta)k_{i}+v_{i}-\alpha
e_{i}\leq(1-\beta)+6-6\alpha=\frac{25}{8}\leq 2\beta$.

  7. (VII.)

If $l=3$ and $p=0$, then by Lemma 3.6, we have $(1-\beta)k_{i}+v_{i}-\alpha
e_{i}\leq(1-\beta)+6-6\alpha=\frac{25}{8}\leq 2\beta$.

  8. (VIII.)

If $l=3$ and $p=1$, then by Lemma 3.6, we have either
$(1-\beta)k_{i}+v_{i}-\alpha e_{i}\leq(1-\beta)+6-7\alpha=\frac{22}{8}\leq
2\beta$ or $(1-\beta)k_{i}+v_{i}-\alpha e_{i}\leq(1-\beta)+7-9\alpha=3\leq
2\beta$.

  9. (IX.)

If $l=2$ and $p=1$, then by Lemma 3.6, we have $(1-\beta)k_{i}+v_{i}-\alpha
e_{i}\leq 5-5\alpha=\frac{25}{8}\leq 2\beta$.

  10. (X.)

If $l=1$ and $p=0$, then by Lemma 3.6, we have $(1-\beta)k_{i}+v_{i}-\alpha
e_{i}\leq 4-2\alpha=\frac{13}{4}=2\beta$.

  11. (XI.)

If $l=4$ and $p=4$, then by Lemma 3.6, we have $(1-\beta)k_{i}+v_{i}-\alpha
e_{i}\leq 7-10\alpha=\frac{13}{4}=2\beta$.

  12. (XII.)

If $l=3$ and $p=3$, then by Lemma 3.6, we have $(1-\beta)k_{i}+v_{i}-\alpha
e_{i}\leq 6-8\alpha=3\leq 2\beta$.

  13. (XIII.)

If $l=0$ and $p=0$, then by Lemma 3.6, we have either
$(1-\beta)k_{i}+v_{i}-\alpha e_{i}\leq 3-\alpha=\frac{21}{8}\leq 2\beta$, or
$(1-\beta)k_{i}+v_{i}-\alpha e_{i}\leq-(1-\beta)+2=\frac{21}{8}\leq 2\beta$.

This concludes the proof of the first claim.

For the second claim, suppose $N$ is odd. Note that in $F_{r+1}^{D}$ there is
a leaf $u$ or an isolated vertex $u^{\prime}$. Set $\hat{w}_{r+1}^{S}$ to be
either $u$ or $u^{\prime}$, whichever is present. The first case leads to
removing $2$ vertices and at least $1$ edge, the second leads to removing $1$
vertex, $0$ edges and $1$ isolated vertex. Hence, $\beta\geq
m_{r+1}^{S}(\hat{w}_{r+1}^{S})\geq m_{r+1}^{S}(w_{r+1}^{S})$, as wanted. ∎