1 Introduction
Since its introduction in 2010 [Reference Brešar, Klavžar and Rall6], the domination game has met with a very wide response and has been studied in great detail. The state of the field up to 2021 was summarised in the book [Reference Brešar, Henning, Klavžar and Rall4]. The domination game research is still very topical: in particular, Versteegen [Reference Versteegen28] proved the
$3/5$
-conjecture for the domination game posed in [Reference Kinnersley, West and Zamani20], while Portier and Versteegen [Reference Portier and Versteegen27] proved the
$3/4$
-conjecture for the total domination game posed in [Reference Henning, Klavžar and Rall15]. For selected additional recent achievements, see [Reference Brito, Marcilon, Martins and Sampaio7, Reference Bujtás, Iršič and Klavžar8, Reference Forcan and Mikalački10, Reference Führer, Grasegger, Hametner and Roche-Newton11, Reference Iršič Chenoweth17, Reference James and Vijayakumar18, Reference Worawannotai and Charoensitthichai29].
Sierpiński graphs [Reference Klavžar and Milutinović22] were introduced in connection with various problems and applications, including the Tower of Hanoi game, physics, interconnection networks and topology; see the extensive survey [Reference Klavžar, Hinz and Zemljič21] on the developments up to 2017 and the selected subsequent references [Reference Attarzadeh, Abbasi and Behtoei1, Reference Hinz and Stockmeyer16, Reference Joshwa, Rajan, Rajalaxmi and Cangul19, Reference Liu25, Reference Menon, Chithra and Savitha26, Reference Yang, Li, Mao, Cheng and Klasing30]. A characteristic feature of Sierpiński graphs is their fractal-like structure, which makes them a natural discrete analogue of fractals.
From the algorithmic perspective, domination is a fundamental graph-theoretic problem that is computationally hard in general [Reference Garey and Johnson12], but the domination number can be determined efficiently for several important graph classes. In particular, for Sierpiński graphs
$S_p^n$
, exact formulae for the domination number have been established in [Reference Klavžar, Milutinović and Petr23, Theorem 3.8]: if
$p\ge 1$
and
$n \ge 0$
, then
where
$[n\ \mathrm {even}]$
denotes the Iverson bracket which is, for a given statement
$\mathfrak {S}$
, defined as
$[\mathfrak {S}] = 1$
if
$\mathfrak {S}$
is true, and
$[\mathfrak {S}] = 0$
otherwise. Moreover, the Grundy domination number
$\gamma _{\mathrm {gr}}$
of Sierpiński graphs has been determined in [Reference Brešar, Gologranc and Kos2, Theorem 5]: if
$n, p\ge 1$
, then
Motivated by (1.1) and (1.2), we investigate the domination game played on
$S_p^n$
. Namely, (1.1) can be considered as the game domination number for the case when Dominator is the solitary player, while (1.2) is the solution for the case when Staller is the only player. Hence, it is natural to ask what happens when Dominator and Staller play simultaneously. Having in mind the extensive investigation of the domination game as well as of Sierpiński graphs, it is rather surprising that this problem has not yet been studied.
In the next section, we formally introduce the concepts investigated and recall earlier results which we need. In Section 3, we study the domination game on Sierpiński graphs. In particular, we improve the trivial lower bound given by the domination number and the trivial upper bound given by twice the domination number minus one, or equivalently, by the Grundy domination number. Our main result in this section establishes that, for
$p\geq 3$
and
$n \geq 2$
, both
$\gamma _{\mathrm {g}}(S_p^n)$
and
$\gamma _{\mathrm {g}}^\prime (S_p^n)$
are bounded from below by
$(2p-3)p^{n-2}$
and from above by
$(2p-2)p^{n-2}$
. In Section 4, we then consider the total domination game and prove that if
$p\geq 3$
, then
$\gamma _{\mathrm {{tg}}}(S_p^n) \geq (2p-2)p^{n-2}$
and
$\gamma _{\mathrm {{tg}}}^\prime (S_p^n) \geq (2p-2)p^{n-2}$
.
2 Preliminaries
For a positive integer p, we will use the convention
$[p] = \{1,\ldots , p\}$
. Let
${G = (V(G), E(G))}$
be a graph. A set
$D \subseteq V(G)$
is dominating if each vertex from
$V(G)\setminus D$
has a neighbour in D and is total dominating if each vertex from
$V(G)$
has a neighbour in D. The domination number
$\gamma (G)$
of G is the minimum cardinality of a dominating set of G and the total domination number
$\gamma _{\mathrm {t}}(G)$
of G is the minimum cardinality of a total dominating set of G. A legal dominating sequence in G is a sequence of vertices such that each vertex from the sequence dominates at least one vertex of G that is not dominated by the preceding elements in the sequence. The maximum length of a legal dominating sequence in G is the Grundy domination number of G denoted by
$\gamma _{\mathrm {{gr}}}(G)$
. This invariant was studied for the first time in [Reference Brešar, Gologranc, Milanič, Rall and Rizzi3]. The Grundy total domination number
$\gamma _{\mathrm {{gr}}}^{\mathrm {t}}(G)$
is defined analogously for total domination sequences and was introduced in [Reference Brešar, Henning and Rall5].
The domination game is played on a graph G by Dominator and Staller, which alternately choose vertices of G such that each newly selected vertex dominates at least one vertex not previously dominated. The game is over when there is no vertex available to play. At that time, the set of vertices selected, say X, forms a dominating set of G. Dominator’s aim is to finish the game such that
$|X|$
is as small as possible; Staller’s goal is just the opposite. A D-game is the game in which Dominator has the first move and an S-game is the game in which Staller has the first move. The game domination number,
$\gamma _{\mathrm {g}}(G)$
, of G is the number of moves in a D-game when both players play optimally. The Staller start game domination number,
$\gamma _{\mathrm {g}}^\prime (G)$
, of G is defined analogously for the S-game. The total domination game is played analogously to the domination game, except that each newly selected vertex totally dominates at least one vertex not previously totally dominated. The corresponding invariants are denoted by
$\gamma _{\mathrm {{tg}}}(G)$
and
$\gamma _{\mathrm {{tg}}}^\prime (G)$
.
For a set
$A \subseteq V(G)$
, a partially dominated graph,
$G|A$
is a graph in which vertices from A are considered already dominated. If
$G|A$
is a partially dominated graph, then
$\gamma _{\mathrm {g}}(G|A)$
and
$\gamma _{\mathrm {g}}^\prime (G|A)$
denote the optimal number of moves remaining in D-game and S-game, respectively. Analogously,
$\gamma _{\mathrm {{tg}}}(G|A)$
and
$\gamma _{\mathrm {{tg}}}^\prime (G|A)$
are defined.
Next, we recall several known results on the game domination number and the Staller-start game domination number that will be used throughout the paper.
Theorem 2.1 [Reference Brešar, Klavžar and Rall6].
If G is a graph, then
$\gamma _{\mathrm {g}}(G) \leq 2\gamma (G)-1$
.
Lemma 2.2 (Continuation principle, [Reference Kinnersley, West and Zamani20, Lemma 2.1]).
Let G be a graph and let
$A,B\subseteq V(G)$
. If
$B\subseteq A$
, then
$\gamma _{\mathrm {g}}(G|A)\le \gamma _{\mathrm {g}}(G|B)$
and
$\gamma _{\mathrm {g}}^\prime (G|A)\le \gamma _{\mathrm {g}}^\prime (G|B)$
.
The following important result can be deduced by using the continuation principle.
Theorem 2.3 [Reference Brešar, Klavžar and Rall6, Reference Kinnersley, West and Zamani20].
If G is a graph, then
$|\gamma _{\mathrm {g}}(G)-\gamma _{\mathrm {g}}^\prime (G)| \leq 1$
.
Let G be a graph and
$uv$
be an edge in G. Let
$G_{uv}|\{u',v'\}$
be the graph obtained from
$G - uv$
by adding two new vertices
$u'$
and
$v'$
, adding the two edges
$uu'$
and
$vv'$
, and declaring that both
$u'$
and
$v'$
are dominated. For notational convenience, we write
$G_{uv}$
rather than
$G_{uv}|\{u',v'\}$
.
Theorem 2.4 (Cutting lemma, [Reference Dorbec, Henning, Klavžar and Košmrlj9, Theorem 3.1]).
Let G be a graph and let A,
${B \subseteq V(G)}$
, where
$B\subseteq A$
. If
$uv$
is an edge of G, then
$\gamma _{\mathrm {g}}(G|A) \le \gamma _{\mathrm {g}}(G_{uv}|B)$
and
$\gamma _{\mathrm {g}}^\prime (G|A) \le \gamma _{\mathrm {g}}^\prime (G_{uv}|B)$
.
If
$p \geq 3$
and
$n \geq 1$
, then the Sierpiński graph
$S_p^n$
has the vertex set
$V (S_p^n) = [p]^n$
. We will simplify the notation of a vertex
$(i_1, \ldots , i_n)\in V(S_p^n)$
to
$i_1\cdots i_n$
. Vertices
$i_1\cdots i_n$
and
$j_1 \cdots j_n$
of
$S_p^n$
are adjacent if there exists an index
$h \in [n]$
such that: (i)
$i_t = j_t$
for every
$t < h$
; (ii)
$i_h \neq j_h$
; and (iii)
$i_t = j_h$
and
$j_t = i_h$
for every
$t> h$
. Define the set of vertices
the elements of which are referred to as the extreme vertices of
$S_p^n$
. If
$s \in [p]^{n-k}$
, where
$k \in [n-1]$
, then the subgraph of
$S_p^n$
induced by the vertices of the form
$\{st:\ t \in [p]^k\}$
, is isomorphic to
$S_p^k$
and denoted by
$\underline {s}S_p^{k}$
. For
$i\in [p]$
, the notation
$\underline {i}S_p^{n-1}$
is simplified to
$iS_p^{n-1}$
, in which case, we have
$iS_p^{n-1} \cong S_p^{n-1}$
.
For
$p\ge 3$
, let
$\Gamma _p$
be the graph obtained from
$S_p^2$
by adding a pendant vertex to each of its p extreme vertices. The vertices of
$\Gamma _p$
corresponding to the vertices of
$S_p^2$
will be labelled using the convention for
$S_p^2$
, and the vertices attached to the extreme vertices will be denoted by
$x_1, \ldots , x_p$
, where
$x_i$
is adjacent to
$ii$
. Set also
${X_p = \{x_1,\ldots , x_p\}}$
. In addition, let
$\Gamma _p^-$
be the graph obtained from
$\Gamma _p$
by removing the vertex
$x_p$
and let
$X_p^- = \{x_1,\ldots , x_{p-1}\}$
. In Figure 1, the graphs
$\Gamma _4$
and
$\Gamma _4^-$
are presented.
Graphs
$\Gamma _4$
(left) and
$\Gamma _4^-$
(right).
Figure 1 Long description
The image contains two side-by-side graph diagrams.
Left Graph Gamma sub 4:
- Four outer nodes are labeled x sub 1 at the top-left, x sub 4 at the top-right, x sub 2 at the bottom-left, and x sub 3 at the bottom-right.
- Each outer node connects via a diagonal line to a corner of a central square grid.
- The central grid consists of four smaller 2 by 2 square clusters.
- The top-left cluster is labeled 11, the bottom-left is 22, the bottom-right is 33, and the top-right is 44.
- Each 2 by 2 cluster is a complete graph with all four nodes connected to each other, including internal diagonals.
- The four clusters are linked together to form a larger square frame.
- Two long diagonal lines cross the center of the entire grid, connecting the innermost nodes of the top-left cluster to the bottom-right cluster, and the top-right cluster to the bottom-left cluster.
Right Graph Gamma sub 4 super minus:
- This graph has an identical structure to the left graph but lacks the outer top right node and numerical labels (x sub 1 through x sub 3 and 11 through 44).
- It maintains the similar arrangement of three outer nodes, four internal 2 by 2 complete clusters, and the central crossing diagonal lines.
3 Domination game
In this section, we study the (Staller start) game domination number of Sierpiński graphs. First, combining (1.1) with Theorem 2.1, we get
Since Sierpiński graphs are traceable (in fact, Hamiltonian), this bound confirms Rall’s conjecture for the case of Sierpiński graphs asserting that if G is a traceable graph, then
$\gamma _{\mathrm {g}}(G) \le \lceil |V(G)|/2\rceil $
(see [Reference Brešar, Henning, Klavžar and Rall4, Conjecture 2.41]). Moreover, it also confirms the stronger 1/2-conjecture [Reference Bujtás, Iršič and Klavžar8, Conjecture 1.2] asserting that as soon as
$\delta (G)\ge 2$
, then
${\gamma _{\mathrm {g}}(G) \le \lceil |V(G)|/2 \rceil }$
.
In this section, we first significantly improve (3.1) by showing that the (Staller start) game domination number of
$S_p^n$
is at most
$({2(p-1)}/{p^2})|V(S_p^n)|$
. This implies that, for every fixed p, the game domination number of
$S_p^n$
is bounded above by a constant fraction of its order, namely
${2(p-1)}/{p^2}.$
Next, we improve also the lower bound by showing that the (Staller start) game domination number is at least
$(2p-3)p^{n-2}$
, equivalently
${(2p-3)}/{p^2}$
of its order.
Lemma 3.1. If
$p\ge 3$
, then the following hold:
-
(i) $\gamma _{\mathrm {g}}(\Gamma _p|X_p) = \gamma _{\mathrm {g}}^\prime (\Gamma _p|X_p) = 2p-2$
; -
(ii) $\gamma _{\mathrm {g}}(\Gamma _p^-|X_p^-) = \gamma _{\mathrm {g}}^\prime (\Gamma _p^-|X_p^-) = 2p-2$
.
Moreover, if in each of the cases, Staller decides to skip a move, the corresponding game ends in at most
$2p-2$
moves.
Proof. First, consider the D-game played on
$\Gamma _p|X_p$
. The strategy of Dominator is to play vertices
$1p, 2p, \ldots, (p-1)p$
in his first
$p-1$
moves. If any of these moves is not possible, then he chooses any other legal move. Note that assuming that these
$p-1$
vertices have been played, the only not yet dominated vertex in
$\Gamma _p|X_p$
is the vertex
$pp$
. Hence, no matter how Staller played, they are forced to dominate this undominated vertex in their
$(p-1)$
th move. In this way, Dominator achieves the goal to finish the game in not more than
$2p-2$
moves. Hence,
$\gamma _{\mathrm {g}}(\Gamma _p|X_p) \leq 2p-2$
.
We next show that Staller has a strategy that at least
$2p-2$
vertices will be played on
$\Gamma _p|X_p$
. Note first that during the game, if Dominator has played some move in
$iS_p^1$
, then by the continuation principle, they will not select any other vertex of
$iS_p^1$
in their first
$p-1$
moves. By the same reason, they will never play on
$X_p$
during these moves. Hence, we may assume without loss of generality that no vertex of
$pS_p^1$
was selected by Dominator by this stage of the game. Furthermore, we may assume without loss of generality that in their ith move, Dominator plays in
$iS_p^1$
. Now, the strategy of Staller in their first
$p-2$
moves is to respond in
$iS_p^1$
as soon as Dominator selects the vertex in
$iS_p^1$
. That is, in Staller’s ith move, they always have a legal move in the set
$\{ i(i+1), ip\}$
. In their
$(p-1)$
th move, Staller selects the vertex
$pp$
, because it has not yet been dominated. Thus, at least
$2p-2$
moves are played and hence,
$\gamma _{\mathrm {g}}(\Gamma _p|X_p) \geq 2p-2.$
We can conclude that
$\gamma _{\mathrm {g}}(\Gamma _p|X_p)=2p-2$
.
Second, consider the S-game played on
$\Gamma _p|X_p$
. By the continuation principle, we may assume without loss of generality that the first vertex selected by Staller is
$x_p$
. After that, the strategy of Dominator is as above, that is, to select vertices
$1p,\ldots , (p-1)p$
. After that, all the vertices are dominated which in turn implies that
$\gamma _{\mathrm {g}}^\prime (\Gamma _p|X_p) \leq 2p-2$
. We next show that Staller has a strategy that at least
$2p-2$
vertices will be played on
$\Gamma _p|X_p$
. By the continuation principle, we may assume without loss of generality that Staller plays
$x_p$
in their first move. If Dominator has played some move in
$iS_p^1$
, then by the continuation principle, they will not select any other vertex of
$iS_p^1$
in their first
$p-2$
moves. By the same reason, Dominator will never play on
$X_p$
during these moves. The strategy of Staller in their next
$p-2$
moves is to respond in
$iS_p^1$
as soon as Dominator selects the vertex in
$iS_p^1$
. Thus, after these moves,
$1+2(p-2)$
vertices have been selected. Moreover, at this stage of the game, not all vertices are dominated (there exists
$i\in [p]$
such that no vertex from
$iS_p^1$
has been played) and, hence, Dominator is forced to select at least one more vertex. This already gives us the required conclusion, that is,
$\gamma _{\mathrm {g}}^\prime (\Gamma _p|X_p) \geq 2p-2$
.
Proceeding on similar lines as above, we obtain
$\gamma _{\mathrm {g}}(\Gamma _p^-|X_p^-) = \gamma _{\mathrm {g}}^\prime (\Gamma _p^-|X_p^-) = 2p-2$
for any
$p \geq 3$
.
For the case of the game where Staller decides to skip a move, Dominator keeps their strategy described above of playing
$1p,2p,\ldots , (p-1)p$
. Since Staller skipped at least one move, at most
$2p-3$
vertices have been played so far. Since at that point only the vertex
$pp$
is not yet dominated, we can conclude that at most
$2p-2$
vertices are played also if Staller decides to skip a move.
Lemma 3.2. If
$p\geq 3$
, then
$\gamma _{\mathrm {g}}(S_p^2|\mathrm {Ex}(S_p^2)) \geq 2p-3$
and
$\gamma _{\mathrm {g}}^\prime ({S_p^2| \mathrm {Ex}}(S_p^2)) \geq 2p-3$
. Moreover, if Dominator decides to skip a move, the corresponding game will not end in fewer than
$2p-3$
moves.
Proof. Let us start with the D-game played on
$S_p^2|\mathrm {Ex}(S_p^2)$
. Consider the first
$p-2$
moves of Dominator. By the continuation principle, without loss of generality, we may assume that these
$p-2$
vertices belong to
$iS_p^1$
, where
$i\in [p-2]$
. The strategy of Staller is then to reply to each move of Dominator in the same copy of
$iS_p^1$
, which is possible using the same arguments as in the proof of Lemma 3.1. Note that each of these
$2p-4$
selected vertices dominates at most
$2p-4$
vertices from
${V((p-1)S_p^1) \cup V(pS_p^1)}$
. As a consequence, at least two vertices are not yet dominated and, hence, Dominator is forced to play at least one more move. Thus,
${\gamma _{\mathrm {g}}(S_p^2|\mathrm {Ex}(S_p^2)) \geq 2p-3}$
.
In the S-game, Staller follows the same strategy as above. By the continuation principle, we may assume without loss of generality that Staller selects the vertex
$11$
in their first move. After that, Staller’s strategy is as above, that is, whenever Dominator selects a vertex from
$iS_p^1$
, where
$i\neq 1$
by the continuation principle, Staller replies by an arbitrary playable vertex from
$iS_p^1$
. In this way, after the first
$1+2(p-3)$
moves, there exists at least two copies of
$S_p^1$
in
$S_p^2|\mathrm {Ex}(S_p^2)$
such that none of its vertices were selected, say
$iS_p^1$
and
$jS_p^1$
. Hence, after the next move of Dominator, say in
$iS_p^1$
, the vertex
$j1$
is still not dominated. Thus, Staller will have another move, which implies that
${\gamma _{\mathrm {g}}^\prime (S_p^2|\mathrm { Ex}(S_p^2)) \geq 2p-3}$
.
For the case where Dominator decides to skip a move, Staller keeps their strategy described above to reply to each move of Dominator in the same copy of
$iS_p^1$
. Whenever Dominator decides to skip a move, Staller plays (if possible) inside those copies of
$iS_p^1$
in which a vertex has already been played. If no such legal move exists, then Staller will play the extreme vertex of a not yet played
$iS_p^1$
. By this strategy, Staller can guarantee that at least
$2p-3$
vertices are played.
Theorem 3.3. If
$p\geq 3$
and
$n\ge 2$
, then
$(2p-3)p^{n-2} \leq \gamma _{\mathrm {g}}(S_p^n), \gamma _{\mathrm {g}}^\prime (S_p^n) \leq (2p-2)p^{n-2}.$
Proof. The statement can be checked easily for
$n=2$
; hence, we assume in what follows that
$n \geq 3$
. First, we prove that
$\gamma _{\mathrm {g}}(S_p^n) \leq (2p-2)p^{n-2}$
. Fix
$n\ge 3$
and
$p\ge 3$
, and set
Note that
$E_2$
contains the edges that connect different copies of
$S_p^2$
; see Figure 2, where these edges are dotted in the case
$S_3^4$
. Let
$G_{n,p}$
be the graph obtained from
$G=S_p^n$
by inductively using operation
$G_{uv}$
for every edge
$uv \in E_2$
. Note that
$G_{n,p}$
consists of
$p^{n-2}$
components, p of them being isomorphic to
$\Gamma _p^-$
and the rest isomorphic to
$\Gamma _p$
. By Theorem 2.4, it follows that
$\gamma _{\mathrm {g}}(S_p^n) \leq \gamma _{\mathrm {g}}(G_{n,p})$
. Thus, it remains to show that
$\gamma _{\mathrm { g}}(G_{n,p}) \leq (2p-2)p^{n-2}$
. For this, consider the strategy of Dominator always playing optimally, if possible, in the same component of
$G_{n,p}$
in which Staller played the last move. Note that such a move is not possible only if all the vertices of the component in which Staller played last are already dominated. In such a case, provided the game is not over yet, Dominator either plays optimally in a component in which no vertex was played or in a component in which they had the last move. Note that by the strategy of Dominator, Staller will never play two consecutive moves in the same component of
$G_{n,p}$
. By applying Lemma 3.1, it follows that at most
$2p-2$
moves will be played in each component of
$G_{n,p}$
. As there are
$p^{n-2}$
such components, we can conclude that
$\gamma _{\mathrm {g}}(S_p^n) \leq \gamma _{\mathrm {g}}(G_{n,p}) \leq (2p-2)p^{n-2}$
. An analogous strategy of Dominator yields the required result for the S-game.
The Sierpiński graph
$S_3^4$
. The dotted edges are the connecting edges between the copies of
$S_3^2$
in it.
Figure 2 Long description
A large triangular fractal structure composed of smaller interconnected triangles. The graph consists of three main triangular clusters arranged in a larger triangle.
* The top cluster apex is vertex 1111. It branches down into smaller triangles with vertices labeled in four-digit sequences starting with 1. Dotted lines connect vertex 1222 to 2111 on the left, and 1333 to 3111 on the right. A horizontal dotted line connects vertex 1233 to 1322.
* The bottom-left cluster has its apex at 2111. Its base vertices range from 2222 on the far left to 2333 on the right. A horizontal dotted line connects vertex 2233 to 2322.
* The bottom-right cluster has its apex at 3111. Its base vertices range from 3222 on the left to 3333 on the far right. A horizontal dotted line connects vertex 3233 to 3322.
* A central horizontal dotted line connects the bottom-left cluster at vertex 2333 to the bottom-right cluster at vertex 3222.
Each small triangle consists of three vertices and three solid edges. The dotted edges represent the bridges between the primary sub-graphs.
Now, we prove
$\gamma _{\mathrm {g}}(S_p^n) \geq (2p-3)p^{n-2}$
. We partition
$V(S_p^n)$
into
$p^{n-2}$
sets, where each set induces a copy of
$S_p^2$
. Staller’s strategy is the following. Staller always plays optimally, if possible, in the same partition set in which Dominator played their last move, where optimal play is with respect to the graph
$S_p^2|\mathrm {{Ex}(S_p^2)}$
. Note that such a move is not possible only if all the vertices of the partition set in which Dominator played last are already dominated. In such a case, provided the game is not yet over, Staller either plays optimally in a partition set in which no vertex was played or in a partition set in which they had the last move. Note that by the strategy of Staller, Dominator will never play two consecutive moves in the same partition set of
$S_p^n$
. By applying Lemma 3.2 and by the continuation principle, it follows that at least
$2p-3$
moves will be played in each of the partition sets. Thus,
$\gamma _{\mathrm {g}}(S_p^n) \geq (2p-3)p^{n-2}$
. An analogous strategy of Staller yields
$\gamma _{\mathrm {g}}^\prime (S_p^n) \geq (2p-3)p^{n-2}$
.
4 Total domination game
In this section, we study the total domination game on Sierpiński graphs. We will make use of the total continuation principle for the total domination game, whose formulation is identical to that for the continuation principle, with
$\gamma _{\mathrm {g}}(G)$
and
$\gamma _{\mathrm {g}}^\prime (G)$
respectively replaced by
$\gamma _{\mathrm {{tg}}}(G)$
and
$\gamma _{\mathrm {{tg}}}^\prime (G)$
.
As with the domination number, determining the total domination number is computationally hard for general graphs [Reference Garey and Johnson12]. For Sierpiński graphs, however, this parameter can be determined efficiently. In [Reference Gravier, Kovše, Mollard, Moncel and Parreau13], it was shown that
However, for the Grundy total domination number, which corresponds to the maximum length of a legal total dominating sequence, it was shown in [Reference Kos24, Corollary 3.59] that
Next, we consider the game total domination number on Sierpiński graphs and show that it lies strictly between these two extreme options, in which either just Dominator (in (4.1)) or just Staller (in (4.2)) is playing the game.
The relation
$\gamma _{\mathrm {{tg}}}(G) \leq 2\gamma _{\mathrm {t}}(G) -1$
from [Reference Henning, Klavžar and Rall14, Theorem 3.1] applied to Sierpiński graphs yields
Next, we improve a trivial lower bound
$\gamma _{\mathrm {{tg}}}(S_p^n) \geq \gamma _{\mathrm {t}}(S_p^n)$
as follows. We start with a partial result that will be needed in the proof.
Lemma 4.1. If
$p\geq 3$
, then
$\gamma _{\mathrm {{tg}}}(S_p^2|\mathrm {Ex}(S_p^2)) \geq 2p-2$
and
$\gamma _{\mathrm {{tg}}}^\prime ({S_p^2|\mathrm {Ex}}(S_p^2)) \geq 2p-2$
. Moreover, if Dominator decides to skip a move, the corresponding game will last at least
$2p-2$
moves.
Proof. Let us start with the D-game played on
$S_p^2|\mathrm {Ex}(S_p^2)$
. Staller plays using the following strategy. If Dominator plays in
$iS_p^1$
for some
$i\in [p]$
, then Staller selects
$ii$
, if possible; otherwise, Staller selects an arbitrary vertex from
$V(iS_p^1)\setminus \{ii\}$
. Note that by this strategy, Staller totally dominates exactly one new vertex in each of their moves. Consider now the first
$p-1$
moves of Dominator. By the total continuation principle and Staller’s strategy, without loss of generality, we may assume that these
$p-1$
vertices belong to
$iS_p^1$
, where
$i\in [p-1]$
, and each move of Dominator can totally dominate at most
$p-1$
vertices previously not totally dominated. After
$2p-3$
moves and including the p pre-totally dominated vertices, at most
$(p-1)^2 + (p-2) + p = p^2 - 1$
vertices have been totally dominated. At least one vertex is not yet totally dominated and, hence, Staller is able to play at least one more move. Thus,
$\gamma _{\mathrm {{tg}}}(S_p^2|\mathrm {Ex}(S_p^2)) \geq 2p-2$
.
In the S-game, let Staller, by their strategy, first play vertex
$11$
and thus they totally dominate
$p-1$
vertices that were not previously totally dominated. Staller’s strategy for the next
$p-3$
moves is as above, that is, whenever Dominator selects a vertex from
$iS_p^1$
, where
$i\neq 1$
, by the total continuation principle, Staller replies by an arbitrary playable vertex from
$iS_p^1$
. In this way, after
$2p-5$
moves, there are at least two indices
${i,j \in [p]\setminus \{1\}}$
, such that no vertex from
$iS_p^1$
and
$jS_p^1$
was played until this stage of the game. By the total continuation principle, Dominator in their next move chooses a vertex from
$V(iS_p^1) \cup V(jS_p^1)$
, say a vertex from
$iS_p^1$
. Hence, after
$2p-4$
moves, at most
$(p-1)+(p-3)+(p-1)(p-2) +p = p^2 -2$
vertices are totally dominated. In particular, the vertices
$j1$
and either
$ji$
or
$ij$
are not yet totally dominated. Staller's next move is to play vertex
$1j$
. Since this leaves either
$ji$
or
$ij$
not yet totally dominated, the game continues. This implies that
$\gamma _{\mathrm {{tg}}}^\prime (S_p^2|\mathrm {Ex}(S_p^2)) \geq 2p-2$
.
For the case of the game where Dominator decides to skip a move, Staller keeps their strategy described above to reply to each move of Dominator in the same copy of
$iS_p^1$
. Whenever Dominator decides to skip a move, Staller plays (if possible) inside those copies of
$iS_p^1$
in which a vertex has already been played. If no such legal move exists, then Staller will play the extreme vertex of a not yet played
$iS_p^1$
. By this strategy, Staller can guarantee that at least
$2p-2$
vertices are played.
Theorem 4.2. If
$p \geq 3$
and
$n\geq 2$
, then
$\gamma _{\mathrm {{tg}}}(S_p^n),\gamma _{\mathrm {{tg}}}^\prime (S_p^n) \geq (2p-2)p^{n-2}$
.
Proof. Consider first the case
$n=2$
. Then, the total continuation principle implies that
$\gamma _{\mathrm {{tg}}}(S_p^2) \geq \gamma _{\mathrm {{tg}}}(S_p^2|\mathrm {{Ex}}(S_p^2))$
, as well as
$\gamma _{\mathrm {{tg}}}^\prime (S_p^2) \geq \gamma _{\mathrm {{tg}}}^\prime (S_p^2|\mathrm {{Ex}}(S_p^2))$
. Furthermore,
$\gamma _{\mathrm {{tg}}}(S_p^2|\mathrm {{Ex}}(S_p^2)) \geq 2p-2$
and
$\gamma _{\mathrm {{tg}}}^\prime (S_p^2|\mathrm {{Ex}}(S_p^2)) \geq 2p-2$
by Lemma 4.1, which finishes the case
$n=2$
. Thus, we may now assume that
$n \geq 3$
.
We partition
$V(S_p^n)$
into
$p^{n-2}$
sets where each set induces a copy of
$S_p^2$
. Staller’s strategy is the following. Staller always plays optimally, if possible, in the same partition set in which Dominator played their last move, where optimal play is with respect to the graph
$S_p^2|\mathrm {{Ex}(S_p^2)}$
. Note that such a move is not possible only if all the vertices of the partition set in which Dominator played last are already dominated. In such a case, provided the game is not yet over, Staller either plays optimally in a partition set in which no vertex was played or in a partition set in which they had the last move. Note that by the strategy of Staller, Dominator will never play two consecutive moves in the same partition set of
$S_p^n$
. By applying Lemma 4.1 and the total continuation principle, it follows that at least
$2p-2$
moves will be played in each of the partition sets. Thus,
$\gamma _{\mathrm {{tg}}}(S_p^n) \geq (2p-2)p^{n-2}$
. An analogous strategy of Staller yields
$\gamma _{\mathrm {{tg}}}^\prime (S_p^n) \geq (2p-2)p^{n-2}$
.
The three parameters therefore exhibit three different scales of behaviour. The total domination number is equal to
$p^{n-1}$
, while our results show that
Thus, the game total domination number is confined to a narrow interval around
$2p^{n-1}$
. In contrast, the known lower bound for the Grundy total domination number yields
Consequently, the parameters
$\gamma _{\mathrm {t}}$
,
$\gamma _{\mathrm {{tg}}}$
and
$\gamma _{\mathrm {{gr}}}^{\mathrm {t}}$
can be roughly viewed as being of sizes
respectively. In particular, whereas the total domination game increases the size of a minimum total dominating sequence by at most a factor of
$2$
, the Grundy total domination number may be larger by a factor that grows linearly with p.
