In this paper we study a new graph parameter, the stacking number. Defined in relation to the eternal domination game, we show that there are highly connected graphs for which it is beneficial to allow multiple guards to occupy a vertex, answering an open question of Finbow et al. In fact, we show that for any sequence \( (s_i) \), allowing \( s_j \) guards to occupy a vertex can save arbitrarily many guards in comparison to allowing fewer than this on a vertex. We also show that the stacking number is \( 1 \) for all trees.
The eternal domination game is a two player game played on a graph \(G\) between an attacker and a defender. Taking turns, the attacker selects a vertex to attack, and the defender must defend against the attack by moving one of the guards they control on to the attacked vertex (other guards may also move). If the defender is ever unable to defend against an attack, the attacker wins. Otherwise, the defender wins. The most well studied aspect of this problem is the eternal domination number, defined as the minimum number of guards the defender needs in order to win.
This problem was introduced by Burger et al. [1], where the problem considered had the additional restriction of only allowing a single guard to move in response to an attack. In this model they were able to show that there is no benefit to allowing multiple guards to occupy a vertex. Goddard et al. [3] conjectured that there would similarly be no benefit to allowing multiple guards on a vertex when all guards are allowed to move. This was shown to be false by Finbow et al. [2] who showed that there are graphs for which it is beneficial to allow \(2\) guards to occupy a vertex, and that the number of guards this saves can be arbitrarily large.
An example of their construction can be seen in Figure 1. The numbers indicate the number of guards on that vertex. When only \(1\) guard is allowed to occupy a vertex, \(9\) guards are needed whereas when \(2\) or more are allowed, \(8\) guards suffices. This implies that the stacking number for this graph is at least \(2\). In Theorem 3.8 we show that this is the minimum number of guards needed in all cases, and that this graph has stacking number exactly \(2\).
In this paper we use \(D_S(G;k)\) to denote the eternal domination number of \(G\) when at most \(k\) guards are allowed to occupy a vertex. We use \(D_S(G;\infty)\) to denote the number of guards needed to eternally dominate \(G\) when any number of guards may occupy a vertex. Clearly as we increase \(k\), the number of guards needed does not increase, and the minimum is achieved when we allow any number of guards to occupy a vertex. This is summarized by the following proposition:
Proposition 1.1. For any graph \(G\) and integer \(k\), we have \[D_S(G;\infty)\leq D_S(G;k)\leq D_S(G;1).\]
The minimum number of guards required to defend \(G\) is \(D_S(G;\infty)\). Clearly there is no advantage to placing more than \(D_S(G;\infty)\) guards on a single vertex, and as such there exists some minimum \(l_0\) such that \(D_S(G;l_0)=D_S(G;\infty)\). We refer to this number as the stacking number of \(G\), which we denote by \(S(G)\). Phrased in terms of this new parameter, the results of Finbow et al. show that there are graphs which have stacking number at least \(2\). However, the graphs they constructed all contain a cut-vertex, leading them to pose the following problem:
Problem 1.2 . [1] Is true that for any integer \(c\), there exists a \(2\)-connected graph such that \(D_S(G;1)-D_S(G;\infty)\geq c\)?
In Section 3 we answer Problem 1.2 in the affirmative and in the process show that for any \(k\) and \(s\), there are infinitely many \(k\)-connected graphs with stacking number \(s\). In Section 4 we show that if \(T\) is a tree, then \(S(T)=1\).
Let \(G=(V,E)\) be a graph. We use \(N(v)\) and \(N[v]\) to denote the open and closed neighbourhoods of the vertex \(v\) respectively, where \[\begin{aligned} N(v)&=\{u : uv\in E(G)\}, \\ N[v]&=N(v)\cup \{v\}. \end{aligned}\]
If \(S\) is a set of vertices, the open and closed neighbourhoods of \(S\) are defined similarly: \[\begin{aligned} N(S)&=\{u : u \in N(v) \text{ for some $v\in S$}\}\setminus S, \\ N[S]&= N(S)\cup S. \end{aligned}\]
A set \(D\subseteq V\) is called a dominating set if for all \(v\in V\) either \(v\in D\) or \(v\) has some neighbour \(u \in D\). Alternatively, \(D\) is a dominating set if \(N[D]=V(G)\). The size of a minimum dominating set for a graph \(G\) is denoted as \(\gamma(G)\).
The main results of this paper concern the eternal domination game, played on a graph \(G\) between two players, the Attacker and the Defender. We give the specific rules of this game shortly, but begin with some necessary preliminary definitions. For some fixed \(k\), the Defender controls a set of \(k\) mobile guards who occupy the vertices of the graph. Formally, this can be treated as a function \(c: V\rightarrow 2^{[k]}\) such that \(\{c(v) : v\in V\}\) forms a partition of \([k]\). We refer to such an assignment as a \(k\)-configuration (of guards)1, and use the notation \(S_c\) to denote the set of vertices which have a guard on them, i.e. \(S_c=\{ v : |c(v)|\geq 1\}\). A configuration is called a dominating configuration if \(S_c\) is a dominating set of \(G\).
We say that two \(k\) configurations \(c_1\) and \(c_2\) can reconfigure to one another if it is possible to move the guards in \(c_1\) to adjacent vertices such that they form \(c_2\). Note that we explicitly allow all guards to move.
Given a graph \(G\), the \(k\) eternal domination game is a game played on \(G\) between two players, the Attacker and the Defender. To begin, the Defender places \(k\) guards on the vertices of \(G\) such in some \(k\) dominating configuration. The Attacker and Defender then take turns doing the following:
The Attacker selects some vertex \(t\) of \(G\) to attack.
The Defender defends against the attack by reconfiguring their guards so that the result is a dominating configuration with a guard on \(t\).
The Attacker wins if the Defender is unable to defend against an attack. Otherwise, the Defender wins. The minimum value of \(k\) for which the Defender has a winning strategy is known as the eternal domination number of \(G\), denoted here as \(D(G)\).
We note that the above definition explicitly allows an arbitrary number of guards to occupy a single vertex in each configuration. As mentioned in the introduction, this paper is concerned with the variation of limiting the number of guards allowed to occupy any given vertex. As such, we use the notation \(D_S(G;l)\) to denote the minimum number of guards needed for the Defender to win the game of eternal domination when they are allowed to place at most \(l\) guards on a vertex in any configuration of their strategy.
The stacking number of a graph is then the minimum \(l_0\) such that \(D_S(G;l_0)=D(G)\). We denote this as \(S(G)\). In other words, it is the minimum number of guards we must allow to occupy a vertex in order for the Defender to have a strategy which uses the minimum number of guards over all strategies without restriction. This is equivalent to saying \(l\) is the maximum number of guards which occupy a vertex in any configuration in any optimal strategy when minimized over all strategies.
The name stacking number is in reference to the notion of the guards being physical tokens occupying vertices, and needing to stack them on one another when multiple occupy a vertex. As mentioned in the introduction, the stacking number can be viewed as an example of how the number of guards needed may drop as the number of guards allowed to occupy a vertex increases. Accordingly, we define the stacking sequence of a graph \(G\) as \(D_S(G;1), D_S(G;2),\ldots,D_S(G;\infty)\). The stacking number and the stacking sequence are clearly related, as the stacking number is simply the maximum index \(i\) such that \(D_S(G;i-1)>D_S(G;i)\).
We seek to show that for any \(k\) and \(s\) there are infinitely many \(k\)-connected graphs with stacking number \(s\). To accomplish this, we construct a graph we refer to as an airport. This graph is constructed from several pieces called wings, gates, and terminals, defined below:
Let \(k\geq 1\) and \(s\geq 2\) be integers. We refer to copies of \(K_{k+2}-e\) as a \(k\)–terminal or simply a terminal if \(k\) is clear. If the missing edge is \(e=uv\) then we will call the vertices \(u\) and \(v\) the matched pair of the terminal, and the rest of the vertices the gates.
Let \(W(k,s)\) be the graph defined as follows:
Begin by taking \(s\) disjoint \(k\)-terminals.
Attach a universal vertex \(u\).
We call such a graph a wing with capacity \(s\). For a given wing \(W\), we will denote its universal vertex by \(u_W\). See Figure 2 for an example of these graphs within our larger construction.
Note that for a wing \(W\), removing \(u_W\) disconnects the graph. However, removing any other \(k-1\) vertices does not do so. We will use several wings to construct the final graph we are interested in. Now, take the following assumptions:
Let \(k\geq 1\) be a positive integer;
\(S=\{s_i\}\) be some strictly increasing finite sequence of integers bounded below by \(2\);
\(C=\{c_i\}\) be some finite sequence of integers such that for each \(i\) we have \(2ks_i<c_i\).
Then, construct the graph \(G(k, S, C)\) as follows:
For each \(i\), add \(c_i\) distinct copies of \(W(k, ks_i)\), labelled \(W_{i,1},\ldots,W_{i,c_i}\).
Add a copy of \(K_k\), denoted \(B\), disjoint from all wings2.
Join the vertices of \(B\) to the gates of each terminal by adding all possible edges between them.
We call \(G(k,S,C)\) an airport. See Figure 2 for an example of each piece of this construction.
We can now begin proving results about these graphs, beginning with a few useful lemmas.
Lemma 3.1. Let \(W=W(k,s)\) be a wing with universal vertex \(u_W\). Then \(D(W)=2\).
Proof. We first demonstrate that there is an eternal dominating strategy for \(W\) using two guards. As usual, let \(u_W\) be the universal vertex in \(W\); we will maintain a guard on \(u_W\) at all times. Place the other guard on an arbitrarily chosen vertex. If some vertex \(t\) is attacked, we can move the guard on \(u_W\) to \(t\) and the other guard to \(u_W\).
To see that a single guard is insufficient, observe that the only way to form a dominating configuration with one guard is to place that guard on \(u_W\). If some vertex other than \(u_W\) is then attacked, we must necessarily move the guard to that vertex, and thus no longer have a dominating configuration. The result follows. ◻
Lemma 3.2. Let \(W=W(k,s)\) be a wing with universal vertex \(u_W\). Let \(W'\) be the graph obtained by joining the gates of \(W\) to a clique (of any size) with all possible edges. If \(D\subseteq V(W')\) is a dominating set not containing \(u_W\), then \(D\) must contain at least one vertex from each terminal.
Proof. Suppose for contradiction that \(D\) does not contain any vertices in some terminal. Let \(x\) and \(y\) be the matched pair in this terminal. These vertices are only adjacent to the gates of their terminal and \(u_W\), and so \(D\) is not a dominating set. ◻
Lemma 3.3. Let \(G=G(k,S,C)\) be an airport. Consider playing the eternal domination where \(s\) guards are allowed to occupy a vertex on \(G\). In any winning strategy, there must be there must be at least two guards on each wing with strictly more than \(s\) terminals at the end of each round.
Proof. Suppose for contradiction that the Defender has a winning strategy where they end a round in some configuration \(c\) which places fewer than \(2\) guards on some wing \(W\). If we have at most one guard and there is no guard on \(u_W\), then we clearly do not have a dominating configuration, which is a contradiction.
We now consider the case where there is exactly \(1\) guard on \(W\), located on \(u_W\). Let \(v_1\) be a vertex in some matched pair in \(W\) and consider attacking it. The guard on \(u_W\) must move to defend against this attack. Any resulting configuration will not have a guard on \(u_W\) and thus by Lemma 3.2 we must have at least one guard on each terminal. The only guards that can move into the terminals must come from \(B\), and by construction there can be at most \(kj\) of them. However, since \(j<s_i\), we have \(kj<ks_i\) and so the resulting configuration cannot be a dominating set. The claim follows. ◻
We can now begin the proof of our main results. We first show that \(G(k,S,C)\) is \(k\)-connected.
Lemma 3.4. The graph \(G(k, S, C)\) is \(k\)-connected.
Proof. Let \(G=G(k,S,C)\), with \(B\) given as above. Let \(R\) be some set of \(k-1\) vertices, and consider \(G'=G\setminus R\). We will show that \(G'\) is connected, thus implying that \(G\) is \(k\)-connected.
As \(|B|=k\), there must be some vertex \(v\in B\) such that \(v\not\in R\). We will show that there is a walk from any other vertex in \(G'\) to \(v\). Let \(u\neq v\) be some vertex in \(G'\). If \(u\in B\), or \(u\) is a gate in some terminal, then \(uv\in E(G')\) and there is trivially a walk from \(u\) to \(v\).
Let \(T\) be some terminal in wing \(W_{i,j}\). By construction \(T\) has \(k\) gates and thus there must be at least one gate remaining. Call this vertex \(g\). The vertices of the matched pair in \(T\) are adjacent to \(g\), as is the universal vertex of \(W_{i,j}\). Thus there is a walk from each of these vertices to \(v\). The result follows. ◻
We approach the problem of determining the values of an airport’s stacking sequence in four parts, each below. Parts of these proofs are based on the proof of Theorem 2 in [2].
Lemma 3.5. Let \(G=G(k, S, C)\) be an airport with stacking sequence \((a_j)\). If \(j<s_1\), then \(a_j=1+\sum\limits_{l=1}^{|S|} 2c_l\).
Proof. We need to show that when up to \(s_1\) guards are allowed to stack, it is both necessary and sufficient to use \(1+\sum\limits_{l=1}^{|S|} 2c_l\) guards to eternally dominate \(G\).
To see that this number of guards is sufficient, note that by Lemma 3.1 we can defend each wing with \(2\) guards. This leaves only \(B\), which can be trivially defended using a single guard as it is a clique.
We now show that \(D_S(G;1)\geq 1+\sum\limits_{l=1}^{|S|} 2c_l\). Suppose we have only \(\sum\limits_{l=1}^{|S|} 2c_l\) guards. By Lemma 3.3 we must have at least \(2\) guards in each wing at the end of each round, and thus there can be no guards in \(B\) at the end of a round. This means it is impossible to defend against an attack on a vertex in \(B\), a contradiction. Thus, we need at least \(1+\sum\limits_{l=1}^{|S|} 2c_l\) guards, and the result follows. ◻
Recall that the wings of an airport are labelled as \(W_{i,j}\) where \(i\) is the capacity of the wing, and \(j\) is simply an arbitrary label.
Lemma 3.6. Let \(G=G(k, S, C)\) be an airport with stacking sequence \((a_j)\). Fix \(1\leq i \leq |S|\) and let \(K=\sum\limits_{l=1}^i c_l +\sum\limits_{l=i+1}^{|S|} 2c_l+2ks_i\). If \(j\geq s_i\), then \(a_j\leq K\).
Proof. We will prove this result by demonstrating a strategy using \(K\) guards. We will do this by first providing an initial configuration. This configuration splits the guards into several groups depending on their initial locations. We will then show that a configuration satisfying some conditions can defend against an attack on any vertex while still satisfying the conditions. In particular, our initial configuration satisfies these conditions, giving us an eternal dominating strategy. We begin with the initial configuration:
For each wing \(W_{t,r}\) place a guard \(g^U_{t,r}\) on the universal vertex of \(W_{t,r}\).
For each wing \(W_{t,r}\) with \(t>s_i\) place a guard \(g^H_{t,r}\) on some other vertex in \(W_{t,r}\).
Place \(s_i\) guards on each vertex in \(B\), labelled as \(g^B_t\) for \(1\leq t\leq ks_i\).
Arbitrarily place another \(ks_i\) guards on the gates of some wings, labelled \(g^B_t\) for \(ks_i+1\leq t\leq 2ks_i\).
For the sake of notation, let \(g^U\), \(g^H\), and \(g^B\) denote the sets of guards of the form \(g^U_{t,r}\), \(g^H_{t,r}\), and \(g^B_t\) respectively. Observe that this initial configuration uses exactly \(K\) guards and is a dominating configuration as there is a guard on the universal vertex of each wing, and there are (many) guards on the vertices of \(B\).
We may now move on to the second part of this proof. Consider the set of following conditions:
For each wing \(W_{t,r}\), either \(g^U_{t,r}\) is on the universal vertex \(u\) or it is in some terminal \(T\) and each terminal has exactly one guard from \(g^B\) in it.
There are always \(s_i\) guards from \(g^B\) on each vertex of \(B\).
The other guards from \(g^B\) are located in the neighbourhood of \(B\).
For each \(t\) and \(r\), \(g^U_{t,r}\) remains in \(N[u_{W_{t,r}}]\).
Observe that the initial configuration given above satisfies all of these conditions. We will now show that any configuration satisfying these conditions can defend against any attack while still satisfying these conditions.
Suppose we are in some configuration satisfying the conditions above and that some vertex \(v\) has been attacked. We can trivially defend against this attack if \(v\in B\). So suppose \(v\) belongs to some wing \(W_{t,r}\). If \(t > s_i\) we can defend against the attack by Lemma 3.1. So suppose \(t\leq s_i\). We have two further cases depending on the location of \(g^U_{t,r}\):
If \(g^U_{t,r}\) is currently on \(u\), then we can move it to \(v\). By Lemma 3.2 we must move at least one guard to each terminal. We can accomplish this by moving a guard from \(B\) to a gate in each terminal of \(W_{t,r}\). This is always possible as there are at most \(ks_i\) terminals in \(W_{t,r}\), and exactly \(ks_i\) guards on \(B\).
If \(g^U_{t,r}\) is not on \(u\), then it is located in some terminal along with another from \(g^B\). Let \(c\) be the current configuration and consider \(G'=G[S_c\cup\{v\}]\). By our conditions, there is a path from \(g^U_{t,r}\) to \(v\) in \(G\). Let \(P\) be a shortest such path and note that all vertices on \(P\) have a guard on them except \(v\). Consider moving these guards along \(P\) toward \(v\), while swapping the labels of \(g^U_{t,r}\) and the guard which moves to \(v\). We do not need to do any further relabelling as any other guards moved belong to \(g^B\), and the labels of these guards is arbitrary.
In any of the above cases, we may need to make some of the following moves in order to maintain the conditions we began with:
If there are any wings \(W_{t,r}\) with \(t\leq s_i\) which were not attacked and for which \(g^U_{t,r}\) is not located on \(u_{W_{t,r}}\) we move \(g^U_{t,r}\) to \(u_{W_{t,r}}\).
For each guard of \(g^B\) which left \(B\), move some guard of \(g^B\) which began in \(N(B)\) to replace it. Note that this is always possible, as we move at most \(ks_i\) guards out of \(B\) in any round, and by our conditions have exactly \(ks_i\) guards located in \(N(B)\).
To see that our conditions have been maintained, observe the following:
Each wing \(W_{t,r}\) with \(t\leq s_i\) which was not attacked has \(g^U_{t,r}\) on \(u_{W_t}\).
If a wing \(W_{t,r}\) with \(t\leq s_i\) was attacked we have either moved a guard from \(B\) to each terminal, or began with such guards already there.
Each wing \(W_{t,r}\) with \(t > s_i\) always has \(2\) guards in it, one of which is always located on \(u_{W_{t,r}}\).
We never move the guards in \(g^B\) outside of \(N[B]\) and always maintain \(ks_i\) guards on \(B\).
Thus our conditions are always maintained, and so we have an eternal dominating strategy. The result follows. ◻
Lemma 3.7. Let \(G=G(k, S, C)\) be an airport with stacking sequence \((a_j)\). Fix \(1\leq i\leq |S|\) and let \(K=\sum\limits_{l=1}^i c_l +\sum\limits_{l=i+1}^{|S|} 2c_l+2ks_i\). Now,
If \(i\leq |S|-1\) and \(j < s_{i+1}\);
or if \(i=|S|\) and \(j > s_i\),
then \(a_j\geq K\).
Proof. Suppose for contradiction that we have an eternal dominating strategy which uses strictly fewer than \(K = \sum\limits_{l=1}^i c_l + \sum\limits_{l=i+1}^{|S|} 2c_l+2ks_i\) guards. We begin by determining the locations of some of these guards. By Lemma 3.2 there are at least \(\sum\limits_{l=i+1}^{|S|} 2c_l\) guards in the wings with capacity at least \(s_{i+1}\). In order to have a dominating set there must be at least one guard in each wing with capacity at most \(s_i\), so there are at least \(\sum\limits_{l=1}^i c_l\) guards on these wings. This leaves at most \(2ks_i-1\) guards whose locations we have not determined.
By assumption there are at least \(2ks_i+1\) wings of capacity \(s_i\), each of which has \(ks_i\) terminals. Thus there are at least two such wings with exactly one guard on them, call them \(W_{s_i,1}=W_1\) and \(W_{s_i,2}=W_2\) without loss of generality. Let \(g_1\) and \(g_2\) be the guards located on \(W_1\) and \(W_2\) respectively. Consider attacking a matched vertex \(v_1\) in some terminal \(T\) of \(W_1\). Any resulting configuration must place \(g_1\) on the attacked vertex. As \(g_1\) was the only guard in \(W_1\), there cannot be a guard on \(u_{W_1}\). Thus, by Lemma 3.2 we must have a guard on each terminal other than \(T\). Additionally, as \(g_1\) is not adjacent to the other matched vertex in \(T\), we must move another guard to \(T\) as well. Thus, there are now \(ks_i+1\) guards on \(W_1\), and at most \(ks_i-1\) guards whose locations we do not know.
Consider attacking a matched vertex of some terminal \(T'\) of \(W_2\). By a similar argument as before, we must move \(ks_i\) guards to \(W_2\) to defend against this attack. However only \(ks_i-1\) guards can possibly make such moves, so we cannot defend against this attack and obtain a contradiction. The result follows. ◻
We can now combine the above lemmas to give us an exact description of the stacking sequence of an airport.
Theorem 3.8. Let \(G=G(k,S,C)\) be an airport with \(|S|=|C|=l\) and stacking sequence \((a_j)\). Each of the following is true:
If \(j<s_1\), then \(a_j=D_S(G;j)=2\sum\limits_{k=1}^l c_k+1\).
If \(s_i\leq j <s_{i+1}\), then \(a_j=D_S(G;j)=\sum\limits_{k=1}^i c_k +2\sum\limits_{k=i+1}^l c_k+2ks_i\).
If \(s_l\leq j\), then \(a_j=D_S(G;j)=\sum\limits_{k=1}^l c_k +2ks_l\).
Proof. Each claim follows directly from applying the results of Lemmas 3.5, 3.6, and 3.7. ◻
Finally, we show that there are in fact graphs with arbitrary stacking number and connectivity.
Corollary 3.9. For any \(k, s\) there is a \(k\)-connected graph \(G\) with \(S(G)=s\).
Proof. Let \(k\) and \(s\) be given and consider \(G=G(k, (s), (2s+1))\). Recall that the stacking number is equivalent to the last index at which the stacking sequence of \(G\) decreases. By Theorem 3.8 this occurs exactly at \(s\) for \(G\), thus \(S(G)=s\). \(G\) is \(k\)-connected by Lemma 3.4, and the result follows. ◻
We can also use the characterization of the stacking sequence of an airport to show that one can completely specify the location and size of any decreases in a graph’s stacking sequence.
Corollary 3.10. Let \(k\) be some integer and \(A\) some positive non-increasing sequence of integers. Let \(S_i'=(i : a_i-a_{i-1} < 0)\) and let \(C_i'=(2(a_{i-1}-a_i)+1 : i\in S_i)\). Then \(A\) is a stacking sequence for a \(k\)-connected graph when the following conditions hold:
\(\max A = 2\sum c_i'+1\),
\(\min A = k\cdot \max s_i'+\sum c_i'\),
\(2ks_i < c_i\) holds for all \(i\).
Proof. Consider the graph \(G(k, S', C')\). The result then follows from Theorem 3.8. ◻
Corollary 3.11. For any integers \(k\) and \(c\), there exists a \(k\)-connected graph \(G\) such that \(D_S(G;1)-D_S(G;\infty)\geq c\).
Proof. Consider the airport \(G(k,S,C)\) where \(S=(2)\) and \(C=(c+4k)\). The result then follows from Theorem 3.8. ◻
We now show that trees have stacking number \(1\). The proof of this relies on two reductions commonly used for determining the eternal domination number of a tree, known as R1 and R2 [4]. Let \(T\) be a tree:
The reduction R1 can be applied to a vertex \(x\) with \(\deg(x)=2\) and which is adjacent to exactly one leaf, \(y\). It removes both \(x\) and \(y\).
The reduction R2 can be applied to a vertex \(x\) with \(\deg(x)\geq 3\) and which is adjacent to exactly one internal vertex of \(T\). It removes all leaves adjacent to \(x\).
As mentioned these reductions can be used to compute the eternal domination number of a tree by repeatedly applying the following theorem. We will use this result in our proof that all trees \(T\) have \(S(T)=1\).
Theorem 4.1. [4] Let \(T\) be a tree.
If we apply R1 to \(T\) and obtain \(H\), then \(D(T)=D(H)+1\).
If we apply R2 to \(T\) and obtain \(H\), then \(D(T)=D(H)+1\).
Theorem 4.2. Let \(T\) be a tree. Then \(S(T)=1\).
Proof. Let \(T\) be a tree. We will prove this result by induction on both the order and diameter of \(T\). Suppose for induction that the result is true for all trees \(T'\) with \(\textrm{diam}(T')<\textrm{diam}(T)\), and also for all trees \(T'\) where \(\textrm{diam}(T')=\textrm{diam}(T)\) but \(|V(T')|<|V(T)|\). The result is obviously true for trees with diameter at most \(1\). Any tree with diameter \(2\) is a star, and by a similar proof to Lemma 3.1 we can defend \(T\) with \(2\) guards. Clearly, there is no advantage to placing both of these guards on a single vertex. Now, by Theorem 1.1 we need only show that \(D_S(T;\infty)\geq D_S(T;1)\). We have two cases depending on which reductions we can apply to \(T\).
First suppose that we can apply R2 to delete the vertex \(x\) and an adjacent leaf \(y\) from \(T\) to obtain \(T'\). By induction we know that \(D_S(T';\infty)=D_S(T';1)\), and by Theorem 4.1 we know that \(D_S(T;1)=D_S(T';1)+1\). Suppose for contradiction that \(D_S(T;\infty)<D_S(T;1)\); then there is some strategy \(\Lambda\) which allows for \(k\geq 2\) guards to be stacked and uses fewer than \(D_S(T;1)\) guards. Note that in order to maintain a dominating configuration, there must always be a guard on \(x\) or \(y\) in every state of \(\Lambda\). Let \(\Lambda'\) be the strategy where we have removed any moves along the edge connecting \(x\) to the rest of \(T\). Then \(\Lambda'\) must be an eternal dominating strategy when restricted to \(T'\), which uses at most \(D_S(T;\infty)-1\) guards. Thus, \[D_S(T';\infty)\leq D_S(T;\infty)-1<D_S(T;1)-1=D_S(T';1),\] which is a contradiction.
Next suppose that we obtain \(T'\) by applying R1 to delete the leaves \(l_1,\ldots,l_t\), with \(t\geq 2\). By induction we again know that \(D_S(T';\infty)=D_S(T';1)\), and again by Theorem 4.1 we know that \(D_S(T;1)=D_S(T';1)+1\). Suppose for contradiction that \(D_S(T;\infty)<D_S(T;1)\) and let \(\Lambda\) be a strategy which uses this number of guards. We construct an eternal dominating strategy \(\Lambda'\) for \(T'\) as follows: copy \(\Lambda\), and for each state let \(g\) be some guard which is either on \(x\) or some \(l_i\) (guaranteed to exist by definition of a dominating set). Delete \(g\) from that state, and then move any other guards on a leaf \(l_i\) to \(x\). This clearly forms an eternal dominating strategy for \(T'\) which uses \(D_S(T;\infty)-1\) guards, and we again get a chain of inequalities: \[D_S(T';\infty)\leq D_S(T;\infty)-1<D_S(T;1)-1=D_S(T';1),\] which is again a contradiction. Thus \(S(T)=1\) for any tree \(T\). ◻
In this paper we have presented the stacking number, and answered an open question of Finbow et al. [2]. We did so by constructing a specific class of graphs with the desired properties. However, there remain many open questions regarding more general results for this parameter.
Problem 5.1. Which other graphs, provided they exist, have stacking number greater than \(1\)?
Problem 5.2. Are there other classes of graphs for which the stacking number can be bounded, similar to what we have done for trees?
We introduce one last new parameter which may be of interest. Let \(G\) be a graph with \(n\) vertices and \(\Lambda\) an eternal dominating strategy of \(G\). Let \(\sigma_s(G, \Lambda)\) denote the set of vertices in \(G\) which have more than \(s\) guards placed on them in some state of \(\Lambda\). Let \(\Lambda_0\) be an eternal dominating strategy of \(G\) using \(D(G)\) guards taken to minimize the value of \(\frac{|\sigma_s(G,\Lambda_0)|}{n}\). We call the minimum such value the \(s\)-stacking proportion of \(G\). Finally, let \(S^+(s)\) denote the maximum value of the \(s\)-stacking proportion when taken over all graphs.
Corollary 5.3. For any \(s\) we have that \(S^+(s)\geq \frac{1}{2s^2+s+1}\).
Proof. Let \(G=G(k,(s),(2s+1))\) and note that \(G\) has the following number of vertices: \[(2s+1)(s(k+1)+1)+k=k(2s^2+s+1)+(2s+1)^2,\] The stacking number of \(G\) is \(s\), and \(k\) vertices are required have \(s\) guards stacked on them in any optimal strategy. Therefore we get that \[S^+(s)\geq \frac{k}{k(2s^2+s+1)+(2s+1)^2}.\] If we take the limit as \(k\) goes to infinity the result follows. ◻
Problem 5.4. What is the asymptotic behaviour of \(S^+(s)\)? In particular, is it true that \(S^+(s)\in \Omega(1)\)?
The authors would like to acknowledge the advice and help that Dr. Richard Brewster and Dr. Gary MacGillivray provided while working on this paper.