We consider the eternal distance-2 domination problem, recently proposed by Cox, Meger, and Messinger, on trees. We show that finding a minimum eternal distance-2 dominating set of a tree is linear time in the order of the graph by providing a fast algorithm. Additionally, we characterize trees that have eternal distance-2 domination number equal to their domination number or their distance-2 domination number, {along with trees that are} eternal distance-2 domination critical. We conclude by providing general upper and lower bounds for the eternal distance-k domination number of a graph. We construct an infinite family of trees which meet said upper bound and another infinite family of trees whose eternal distance-k domination number is within a factor of 2 of the given lower bound.
Consider the problem of stationing ambulances throughout a city. We desire that each location in the city is close to an ambulance, so that paramedics can respond to a call quickly, but we also need the response time to be maintained after a specific ambulance is assigned to a call. We can model this problem using the notion of eternal domination of a graph, which we outline as follows. Let \(G=(V,E)\) be a graph. Multisets \(S,D \subseteq D\) are adjacent if there exists an ordering \(\{s_1,\dots, s_t\}\) of \(S\) and \(\{d_1,\dots, d_t\}\) of \(D\) where for all \(1\leq i \leq t\), \(s_i\in N[d_i]\). A multiset \(D \subseteq V\) (whose elements are called guards) is an eternal dominating set in \(G\) if for any sequence of vertices \(a_1,\dots, a_N\) (called attacked vertices) there exists a sequence multisets \(D = D_0, D_1,\dots, D_N\) such that for all \(0 \leq i\leq N-1\), \(D_i\) is adjacent to \(D_{i+1}\) and \(a_{i+1} \in D_{i+1}\). The minimum number of guards required, that is the minimum cardinality of an eternal dominating set, is called the eternal domination number of \(G\), and is denoted \(\gamma_{all}^\infty(G)\). Here, the subscript all refers to the fact that each guard is able to move in response to an attack, as introduced by Goddard, Hedetniemi, and Hedetniemi [10], in contrast to the version originally introduced by Burger, Cockayne, Grundlingh, Myndardt, van Vuuren, and Winterbach [3] where only one guard is permitted to move in response to an attack.
Several works have studied the eternal domination number in recent years, as surveyed by Klostermeyer and Mynhardt [14]. Goddard, Hedetniemi, and Hedetniemi [10] established the domination number as a fundamental lower bound and the clique-star cover number as a fundamental upper bound, established exact values for cliques, complete bipartite graphs, paths, cycles, and Cayley graphs, and determined additional upper bounds in terms of the 2-domination number, independence number, and clique-connected cover number. Klostermeyer and MacGillivray [13] provide a linear-time algorithm for determining the eternal domination number of trees. In a subsequent paper, Klostermeyer and MacGillivray [12] characterize trees achieving various upper and lower bounds on the eternal domination number.
The eternal domination number of grids has been extensively studied. Beaton, Finbow, and MacDonald [1] considered the eternal domination number of \(4 \times n\) grids. Finbow, Messinger, and van Bommel [8] established upper and lower bounds on the eternal domination number of \(3 \times n\) grids. Bounds on the eternal domination number of \(5 \times n\) grids were established by van Bommel and van Bommel [18]. Lamprou, Martin, and Schewe [15] provided a general upper bound for grid graphs that is optimal asymptotically. Bounds for strong grid graphs were studied by McInerney, Nisse, and Pérennes [16] and Gagnon, Hassler, Huang, Krim-Yee, McInerney, Zacarías, Seamone, and Virgile [9].
Henning, Klostermeyer, and MacGillivray [11] demonstrated a tight upper bound for connected graphs with minimum degree 2, and improved the bound for the class of cubic bipartite graphs. Cohen, Martins, McInerney, Nisse, Pérennes, and Sampaio [5] studied a generalization called the spy-game, which they show to be NP-hard. Blažej, Křištán, and Tomáš [2] determined bounds and a linear time algorithm for eternal domination numbers of cactus graphs. Finbow, Gaspers, Messinger, and Ottaway [7] demonstrated the advantage of allowing multiple guards to occupy the same vertex, and give exponential-time algorithms for calculating eternal domination numbers. Most results in the literature do not depend on this detail, however some do. Of particular importance to this paper Cox, Meger, and Messinger [6] assume guards can occupy the same vertices. Keeping with this convention, in this work we allow guards to occupy the same vertex.
Here, we assume an ambulance is not limited to moving to an adjacent location, rather they are allowed to move to locations up to distance \(k\) away. Then we can model this relaxed version of the problem using the notion of eternal distance-\(k\) domination of a graph, as introduced by Cox, Meger, and Messinger [6], defined as follows. Let \(G=(V,E)\) be a graph. Multisets \(S,D \subseteq D\) are \(k\)-adjacent if there exists an ordering \(\{s_1,\dots, s_t\}\) of \(S\) and \(\{d_1,\dots, d_t\}\) of \(D\) where for all \(1\leq i \leq t\), \(\mathop{\mathrm{dist}}(s_i,d_i)\leq k\). A multiset \(D \subseteq V\) (whose elements are called guards) is an eternal distance-\(k\) dominating set in \(G\) if for any sequence of vertices \(a_1,\dots, a_N\) (called attacked vertices) there exists a sequence multisets \(D = D_0, D_1,\dots, D_N\) such that for all \(0 \leq i\leq N-1\), \(D_i\) is \(k\)-adjacent to \(D_{i+1}\) and \(a_{i+1} \in D_{i+1}\). The minimum number of guards required, that is the minimum cardinality of an eternal distance-\(k\) dominating set is called the eternal distance-\(k\) dominaton number of \(G\), and is denoted \(\gamma_{all, k}^\infty(G)\). Consider Figure 1 for two graphs whose domination, distance-2 domination, eternal domination, and eternal distance-2 domination numbers are given. Cox, Meger, and Messinger [6] considered general bounds on, the computational complexity of computing, and the exact values for small classes, of \(\gamma_{all,k}^\infty\). Additionally, they developed reductions for trees and present the following open problems:
Question 1.1 ([6]). For what class of graphs, \(\mathcal{G}\), is \(\gamma_k(G) = \gamma_{all, k}^\infty(G)\) for all \(G \in \mathcal{G}\)?
Question 1.2([6]). Let \(\mathcal{G}_{n, m}\) be the family of simple graphs on \(n\) vertices and \(m\) edges. For a fixed \(n\) and \(m\), what are the graphs with the smallest eternal distance-\(k\) domination number, or largest eternal distance-\(k\) domination number?
Question 1.3 ([6]). Given a fixed \(n\) and fixed \(k\), what possible values can \(\gamma_{all, k}^\infty\) take on, for graphs \(G\) of order \(n\)?
Question 1.4([6]). Which graphs \(G\) have the property that \(\gamma_{all, 2}^\infty(G) = \gamma(G)\)? Can we characterize the trees with this property?
Question 1.5 ([6]). Suppose that for every minimum dominating set of a tree \(T\), each vertex in the dominating set has at least two private neighbours. Then is \(\gamma_{all, 2}^\infty(T) = \gamma(T)\)?
In this work, we focus primarily on the case of \(k = 2\) in trees. Our main approach is to consider the low-diameter subgraphs that are most leaf-like; we develop this idea formally in Section 3. Using these reductions, we provide a linear time algorithm for the computation of the eternal distance-2 domination number of trees. We then provide characterizations of trees for which \(\gamma_{all, 2}^\infty = \gamma\), addressing Question 1.4 for the class of trees and allowing us to answer Question 1.5 in the negative. Additionally, we characterize the trees that are eternal distance-2 domination critical, as well as the trees for which \(\gamma_{all, 2}^\infty = \gamma_2\), partially addressing Question 1.1. We conclude by providing general upper and lower bounds for the eternal distance-k domination number of a graph. We construct an infinite family of trees which meet said upper bound and another infinite family of trees whose eternal distance-k domination number is within a factor of 2 of the given lower bound.
We provide the following results relating domination parameters that will be used throughout the paper. We begin with the following bound on the eternal distance-\(k\) domination number in terms of distance domination, as observed by Cox, Meger, and Messinger [6].
Proposition 2.1 ([6]). For any graph \(G\) and integer \(k \ge 2\), \[\gamma_k(G) \le \gamma_{all, k}^\infty(G) \le \gamma_{\left \lfloor \frac{k}{2} \right \rfloor}(G).\]
Equality between \(\gamma(G)\) and \(\gamma_2(G)\) for trees was characterized by Raczek [17], which forces equality of the eternal distance-2 domination number. We state the characterization here and consider the question of equality of the bounds in later sections. If \(T\) is a tree, a vertex \(u\) is a stem if \(\deg(u)\geq 2\) and \(u\) is adjacent to a leaf. Let \(\mathbb{T}\) be the family of all trees \(T\) that can be obtained from sequence \(T_1, \ldots, T_j\) (\(j \ge 1)\) of trees such that \(T_1\) is the path \(P_2\) and \(T = T_j\), such that \(T_{i+1}\) can be obtained recursively from \(T_{i}\) by the operation \(\mathbb{T}_1\), \(\mathbb{T}_2\), or \(\mathbb{T}_3\):
\(\bullet\) Operation \(\mathbb{T}_1\). The tree \(T_{i + 1}\) is obtained from \(T_i\) by adding a vertex \(x_1\) and the edge \(x_1 y\) where \(y \in V(T_i)\) is a stem vertex of \(T_i\).
\(\bullet\) Operation \(\mathbb{T}_2\). The tree \(T_{i + 1}\) is obtained from \(T_i\) by adding a path \((x_1, x_2, x_3)\) and the edge \(x_1 y\) where \(y \in V(T_i)\) is neither a leaf nor a stem vertex in \(T_i\).
\(\bullet\) Operation \(\mathbb{T}_3\). The tree \(T_{i + 1}\) is obtained from \(T_i\) by adding a path \((x_1, x_2, x_3, x_4)\) and the edge \(x_1 y\) where \(y \in V(T_i)\) is a stem vertex in \(T_i\).
Additionally, let \(P_1\) belong to \(\mathbb{T}\). Then the following is established.
Theorem 2.2 ([17]). Let \(T\) be a tree. Then \(T \in \mathbb{T}\) if and only if \(\gamma(T) = \gamma_2(T)\).
We next note the exact value for the eternal distance-\(k\) domination number has been calculated for paths by Cox, Meger, and Messinger [6]. In Section 7 we will see that paths are an extremal family of graphs in terms of eternal distance-\(k\) domination.
Theorem 2.3 ([6]).For \(n \ge 1\) and \(k \ge 1\), \(\gamma_{all, {k}}^\infty(P_n) = \left \lceil \frac{n}{k + 1} \right \rceil\).
We conclude by introducing some other standard notation from graph theory. To characterize the trees that are eternal distance-2 domination critical, we use the concept of the 1-sum of two graphs to build the family. For graphs \(G\) and \(H\), the 1-sum of \(G\) and \(H\) at vertex \(u\) of \(G\) and \(v\) of \(H\) is the graph formed by taking the disjoint union of graphs \(G\) and \(H\) and identifying vertices \(u\) and \(v\). For a graph \(G\) and a set \(S\subseteq V(G)\) we let \(G[S]\) denote the subgraph of \(G\) induced by \(S\). For a graph \(G\) and an integer \(k\), the \(k^{\text{th}}\) power of \(G\), denoted \(G^k\), is obtained from \(G\) by making vertices \(u,v\) in \(V(G)\) adjacent in \(G^k\) if and only if \(\mathop{\mathrm{dist}}(u,v)\leq k\) in \(G\).
Let \(T = (V,E)\) be a tree. We say \(v \in V\) is a \(0\)-leaf if and only if \(v\) is a leaf, and for \(k>0\), we say \(v\) is a \(k\)-leaf if and only if \(v\) is not a leaf and \(k\) is the least positive integer such that \(v\) is adjacent to a \((k-1)\)-leaf and all but at most one of the neighbours of \(v\) are \(t\)-leaves, where \(t<k\). For a \(1\)-leaf, \(u\), let \(L(u)\) be the set of all leaves adjacent to \(u\), and let \(L[u] = L(u) \cup \{u\}\). Given a \(k\)-leaf, \(v \in V\), \(k>1\), let \(L(v) = \cup_{u \in S} L[u]\), where \(S \subseteq N(v)\) is the largest subset of \(N(v)\) such that for all \(u \in S\), \(u\) is a \(t\)-leaf and \(t<k\). Similarly, let \(L[v] = L(v) \cup \{v\}\). We begin by demonstrating that for all \(k>0\), any tree with a sufficiently large diameter contains a \(k\)-leaf.
Lemma 3.1. Let \(T = (V,E)\) be a tree with a vertex \(v\) and distinct leaves \(u\) and \(w\) such that the unique \((u,w)\)-path in \(T\) contains \(v\) as an internal vertex. If \(\mathop{\mathrm{dist}}(u,v),\mathop{\mathrm{dist}}(w,v) \geq t\), then \(v\) is a \(k\)-leaf for \(k \geq t\).
Proof. Let \(T = (V,E)\) be a tree with a vertex \(v\) and distinct leaves \(u\) and \(w\) such that the unique \((u,w)\)-path in \(T\) contains \(v\) as an internal vertex and suppose \(\mathop{\mathrm{dist}}(u,v),\mathop{\mathrm{dist}}(w,v) \geq t\). We induct on \(t\).
To start suppose \(t=1\). As \(v\) is an internal vertex on a path in \(T\), \(v\) has degree at least \(2\). Hence, \(v\) is not a leaf implying \(v\) is a \(k\)-leaf for some \(k\geq 1\). Thus, the claim holds for \(t=1\). Suppose now the claim holds a fixed value of \(t\geq 1\) and suppose \(\mathop{\mathrm{dist}}(u,v),\mathop{\mathrm{dist}}(w,v) \geq t+1\).
Let \(P\) be the unique \((u,w)\)-path in \(T\). As \(t\geq 1\), \(P\) has length at least \(5\) and \(v\) is not adjacent to \(u\) or to \(w\). Then, \(v\) has distinct neighbours \(u'\) and \(w'\) in \(P\) such that \(\mathop{\mathrm{dist}}(u,u')\geq t\) and \(\mathop{\mathrm{dist}}(w,u')\geq t+2\), while similarly \(\mathop{\mathrm{dist}}(u,w')\geq t+2\) and \(\mathop{\mathrm{dist}}(w,w')\geq t\). By induction on \(t\), \(u'\) is a \(a\)-leaf for \(a \geq t\) and \(w'\) is a \(b\)-leaf for \(b\geq t\). Hence, \(v\) is adjacent to a \(a\)-leaf and a \(b\)-leaf. This implies \(v\) is a \(k\)-leaf where \(k\geq \min\{a,b\} + 1 \geq t + 1\). This completes the proof. ◻
Lemma 3.2. Let \(T = (V,E)\) be a tree. If the diameter of \(T\) is at least \(2k\), then there exists a vertex \(v \in V\) which is a \(k\)-leaf.
Proof. Let \(T = (V,E)\) be a tree with diameter at least \(2k\). Let \(P = v_0 v_1 v_2 \ldots v_m\) be a longest path in \(T\). Then \(m\geq 2k\) by our assumption \(T\) has diameter at least \(2k\). Given \(P\) is a longest path and \(T\) is a tree, \(v_0\) and \(v_m\) are leaves. Notice that as \(T\) is a tree, \(\mathop{\mathrm{dist}}(v_0,v_k),\mathop{\mathrm{dist}}(v_m,v_k) \geq k\). Thus, Lemma 3.1 implies \(v_k\) is a \(k'\)-leaf for some \(k'\geq k\). If \(k'=k\), then the proof is complete. Otherwise, \(k'>k\), and the existence of a \(k'\)-leaf in \(T\) implies the existence of a \(t\)-leaf in \(T\) for all \(t < k'\). This implies the existence of a \(k\)-leaf in \(T\) concluding the proof. ◻
Next, we demonstrate a reduction strategy for computing the eternal distance-2 domination number based on 2-leaves.
Lemma 3.3. Let \(T\) be a tree with diameter at least \(4\). If \(v\) is a \(2\)-leaf in \(T\) such that \(T[L(v)]\) has diameter \(2\), let \(T' = T – L[v]\), otherwise, let \(T' = T – L(v)\). Then, \(\gamma_{all,2}^\infty(T) = \gamma_{all,2}^\infty(T') + 1\).
Proof. Let \(T = (V,E)\) be a tree with diameter at least \(4\) and let \(v \in V\) be a \(2\)-leaf. Let \(T'\) be defined as in the statement of the Lemma. We will show \(\gamma_{all,2}^\infty(T) = \gamma_{all,2}^\infty(T') + 1\) by demonstrating that \(\gamma_{all,2}^\infty(T) \leq \gamma_{all,2}^\infty(T') + 1\) and \(\gamma_{all,2}^\infty(T) \geq \gamma_{all,2}^\infty(T') + 1\).
To begin, observe that as \(v\) is a \(2\)-leaf and \(T\) is a tree, there must be at least \(1\) guard in \(L[v]\) in every distance-2 dominating set of \(T\). Otherwise, there exists a vertex in \(L(v)\) which is not distance-2 dominated. Hence, for every eternally distance-2 dominating set there is at least \(1\) guard in \(L[v]\).
Case 1. \(T[L(v)]\) has diameter \(2\).
Then for all vertices \(u \in L[v]\), a guard at \(u\) is within distance \(2\) of every other vertex in \(L[v]\). Hence, the one guard which must be in \(L[v]\) can eternally distance-2 dominate \(L[v]\). This implies that \(\gamma_{all,2}^\infty(T) \leq \gamma_{all,2}^\infty(T') + 1\), as one extra guard is sufficient to guard \(L[v]\), while \(\gamma_{all,2}^\infty(T')\) is sufficient to guard the rest of the graph.
Note that \(\gamma_{all,2}^\infty(T) \geq \gamma_{all,2}^\infty(T') + 1\) follows directly from the fact there must always be a guard in \(L[v]\). This is because if the guard \(g_1\) in \(L[v]\) were to ever move to protect a vertex \(x \in V\setminus L[v]\), then another guard, \(g_2\), would have to enter \(L[v]\) to remain a distance-\(k\) dominating set. Given \(T\) is a tree, this is never advantageous for the guards, as if \(g_2\) is within distance \(2\) of \(L[v]\) while not being in \(L[v]\), this implies \(g_2\) is also within distance \(2\) of \(x\), so \(g_2\) can move directly to \(x\) and \(g_1\) can remain in \(L[v]\).
Case 2. \(T[L(v)]\) has diameter at least \(3\).
Then we will demonstrate \(\gamma_{all,2}^\infty(T) \leq \gamma_{all,2}^\infty(T') + 1\) by providing a winning strategy for the guards using exactly \(\gamma_{all,2}^\infty(T') + 1\) guards. Place \(\gamma_{all,2}^\infty(T')\) guards on \(V \setminus L(v)\) and let them proceed as if playing on \(T'\). Next place an extra guard, \(g_v\), on \(v\). If the attacker attacks vertices in \(V \setminus L(v)\), then let the guards \(\gamma_{all,2}^\infty(T')\) proceed as if playing on \(T'\), while \(g_v\) does not move.
If a vertex in \(L(v)\) is attacked let \(g_v\) defend against the attack, while the other \(\gamma_{all,2}^\infty(T')\) guards respond as if \(v\) was attacked in \(T'\). This will place a guard \(g\) on \(v\). If the next attack is also on \(L(v)\), then let \(g\) move to respond to the attack, while \(g_v\) returns to \(v\) and the guards in \(V \setminus L[v]\) do not move. As long as the attacker attacks vertices in \(L(v)\), guards \(g\) and \(g_v\) continue this strategy where the guard at \(v\) responds, while the other moves to \(v\). Should the attacker attack a vertex outside of \(L(v)\), then the guard currently at \(v\), say \(g\) without loss of generality, assumes the role of one of the \(\gamma_{all,2}^\infty(T')\) guards protecting \(T'\), while the other guard (again without loss of generality) \(g_v\), returns to \(v\). As this returns the game to its initial state, \(\gamma_{all,2}^\infty(T) \leq \gamma_{all,2}^\infty(T') + 1\).
The fact that \(\gamma_{all,2}^\infty(T) \geq \gamma_{all,2}^\infty(T') + 1\) follows by a similar argument as case 1, where it is never advantageous for the guard \(g_v\) whose job it is to protect \(L[v]\) to protect a vertex \(x\) outside of \(L[v]\), as any guard \(g\) which begins outside of \(L[v]\) and would take on the role of defending \(L[v]\) could simply protect \(x\) directly.
This completes the proof as we have shown that \(\gamma_{all,2}^\infty(T) = \gamma_{all,2}^\infty(T') + 1\) as desired in both cases. ◻
Note that the approach used in Lemma 3.3 does not easily extend for \(\gamma_{all,k}^\infty\) when \(k>2\). For an example of this see Figure 2. Note that when \(k>2\), we may conclude that \(\gamma_{all,k}^\infty(T) \leq \gamma_{all,k}^\infty(T') +1\), however we cannot guarantee that this bound reaches equality, because the guard \(g_2\) (see proof of case 1) might have distance greater than \(k\) to \(x\). This is because supposing \(g_1\) starts at \(v\) and \(g_2\) starts at \(z\), \(\mathop{\mathrm{dist}}(v, x) \leq k\) implies that the neighbour of \(v\) not in \(L[v]\), call it \(y\), has \(\mathop{\mathrm{dist}}(x,y) \leq k-1\), while, \(\mathop{\mathrm{dist}}(z,y) \leq k-1\). Hence, \(\mathop{\mathrm{dist}}(z,x) \leq 2k-2\) is an upper bound that cannot be improved. For \(k \leq 2\) this is fine, as \(k \geq 2k-2\), however for \(k>2\), \(k< 2k-2\) implies \(g_2\) may be unable to reach \(x\) in a single move. Notice that Figure 2 can be generalized to all cases \(k \geq 3\) by appending path of length \(k-3\) to each leaf in \(T\) and \(T'\) respectively.
Notably, a similar, although distinct statement to Lemma 3.3 appears as Proposition 3 from [6]. For completeness we state Proposition 3 from [6]. An \(i\)-end-path in a graph \(G\) is a path of length at least \(i\geq 2\) such that at least one endpoint of the path is a leaf and all internal vertices of the path have degree exactly \(2\). Proposition 3 from [6] reads: Let \(P = x_0,x_1,\dots,x_{k+1}\) be a \((k + 1)\)-endpath of a tree \(T\), where \(x_0\) is a leaf. Let \(T' = T – \{x_0,\dots, x_k\}\), then \(\gamma_{all,k}^\infty(T) = \gamma_{all,k}^\infty(T') + 1\).
Notice that Proposition 3 from [6] is equivalent to case.1 from the proof Lemma 3.3 if \(L(x_k) = \{x_0,x_1,\dots, x_k\}\) and \(k=2\). However, we note that trees \(T\) and \(T'\) in Figure 2 are counterexamples to Proposition 3 from [6]. That is, in an identical way to how Lemma 3.3 does not generalize to the \(k>2\) case, Proposition 3 from [6] will not apply to \(k>2\) implying the proposition is in fact false.
When the diameter of the tree is small, the eternal distance-2 domination number can be directly computed as follows.
Lemma 3.4. Let \(T = (V,E)\) be a tree and let \(k>0\) be an integer and let \(d\) be the diameter of \(T\),
\(\bullet\) if \(k < d < 2k\), then \(\gamma_{all,k}^\infty(T) = 2\), and
\(\bullet\) if \(d \leq k\), then \(\gamma_{all,k}^\infty(T) = 1\).
Proof. Recall that [6] showed that for all graphs \(G\) and integers \(k\), \(\gamma_{all,k}^\infty (G) = \gamma_{all,1}^\infty (G^k)\). Suppose \(k < d < 2k\). Then \(T^k\) has a universal vertex but is not a complete graph. This implies \(\gamma_{all,1}^\infty (T^k) = 2\), which implies \(\gamma_{all,k}^\infty (T) = 2\). Now suppose, \(d \leq k\), then \(T^k\) is complete, implying \(\gamma_{all,1}^\infty (T^k) = \gamma_{all,k}^\infty (T) = 1.\) ◻
We conclude this section with an algorithm, based on the previous results, that will allow us to compute the eternal distance-2 domination number in linear time.
Let \(T\) be a tree rooted at a vertex \(r\). We compute the eternal distance-2 domination number of \(T\) as follows:
(a) Set \(\gamma = 0\) and let \(S = \{r\}\) be a stack.
(b) While the stack is not empty, let \(x\) be the top vertex of the stack.
(i) If the subtree of \(T\) consisting of \(x\) and its descendants has depth at least 3, add each child of \(x\) whose subtree has depth at least two to the stack.
(ii) If the subtree of \(T\) consisting of \(x\) and its descendants has depth 2, remove \(x\) from the stack, increment \(\gamma\), and replace \(T\) with \(T – D[x]\) if \(x\) has one child, and \(T – D(x)\) otherwise, where \(D(x)\) is the set of descendants of \(x\).
(iii) Otherwise, remove \(x\) from the stack.
(c) If \(T\) is not empty, increment \(\gamma\).
(d) Return \(\gamma\).
Theorem 3.5. Let \(T\) be a tree. Then the output, \(\gamma\), of algorithm we have just described, for an arbitrary vertex \(r\) of \(T\), is equal to \(\gamma_{all, 2}^\infty(T)\). Moreover, the running time of this algorithm for such an input is linear in the number of vertices.
Proof. We proceed by induction on the number of vertices in the following way, for any rooted tree \(T\) of order less than \(n\) with root \(r\), the algorithm will output \(\gamma_{all, {2}}^\infty(T)\).
As our base case consider a tree \(T =(V,E)\) rooted at a fixed but arbitrary vertex \(r\) which has depth at most 2. Then \(T\) has diameter at most 4. Note in particular that this is the case for all graphs on at most 3 vertices. Suppose \(T\) has diameter at most 2, then by Lemma 3.4, \(\gamma_{all, 2}^\infty(T) = 1\). If \(r\) is a universal vertex of \(T\), then \(T\) has depth 1, so the algorithm returns 1. Otherwise, \(r\) is a leaf and \(T\) has depth \(2\), so \(L[x] = V\), hence, \(T\) is replaced by \(\emptyset\), and the algorithm returns 1. If \(T\) has diameter 3 or 4, then by Lemma 3.4, \(\gamma_{all, 2}^\infty(T) = 2\). We have that \(T\) has depth 2 and \(r\) has multiple children. Thus \(T\) is replaced by the single vertex \(r\), so the algorithm returns 2.
Now let \(T\) be a tree rooted at \(r\) such that \(T\) has depth at least 3. Let \(v\) be the first vertex to appear on top of the stack for which the subtree of \(T\) consisting of \(v\) and its descendants has depth 2; clearly \(v \neq r\), furthermore, it should be clear that a vertex \(v\) will appear at some point during the run-time of the algorithm (as there must exist a descendant of \(r\) with the properties of \(v\) given \(T\) has depth at least \(3\), while vertices on top of the stack of type (a) add vertices to the stack whose subtree has smaller depth, vertices of type (b) are exactly vertices \(v\), while vertices of type (c) are removed from the stack not to be considered again). Then \(v\) is a 2-leaf of \(T\), and the diameter of \(T\) is at least 3. If \(T\) has diameter at most 4, then by Lemma 3.4, \(\gamma_{all, 2}^\infty(T) = 2\). Then \(T\) is replaced with a nonempty tree of diameter at most 2. So the algorithm returns 2 as desired by induction, noting that the steps of the algorithm applied to this tree are a subset of the steps applied to \(T\).
If \(T\) has diameter greater than 4, then the ancestor of \(v\) is not in \(L[v]\). If \(\deg(v) = 2\), then by Lemma 3.3, \(\gamma_{all, 2}^\infty(T) = \gamma_{all, 2}^\infty(T – L[v]) + 1\), which by the induction hypothesis is precisely the value returned by the algorithm. If \(\deg(v) \ge 3\), then by Lemma 3.3, \(\gamma_{all, 2}^\infty(T) = \gamma_{all, 2}^\infty(T – L(v)) + 1\), which by the induction hypothesis is precisely the value returned by the algorithm.
Finally, we observe that each vertex of the tree is only kept on the stack if its corresponding subtree has depth at least 3. When we return to this vertex, its descendants have depth at most 1, so it has depth at most 2, and is therefore removed from the stack. Furthermore, a vertex is considered while not on top of the stack only when its first, second, or third ancestor is on top of the stack during the while loop. Thus, each vertex is considered at most a constant number of times and each consideration is linear time. Therefore, the algorithm runs in linear time. This completes the proof. ◻
In this section we resolve the question posed in [6] of characterizing when a tree has eternal distance-2 domination number equal to its domination number. The primary tool in our analysis is the reduction given in Lemma 3.3. We begin this section by pointing out that there are trees \(T\) where every vertex in a minimum dominating set has at least \(2\) private neighbours, but the eternal distance-2 domination number is arbitrarily far from the domination number. This resolves another question in [6] in the negative.
For an example of such a tree take a star \(K_{1,n}\) and add two leaves to each leaf of \(K_{1,n}\) to form \(T_n\). Then, \(\gamma(T_n) = n\) while every vertex in the unique minimum dominating set in this tree has exactly two private neighbours. However as the diameter of \(T_n\) is \(4\), Lemma 3.4 implies \(\gamma_{all,2}^\infty(T_n) = 2\).
We first note the following lemma which is a special case of Proposition 1 from [6].
Lemma 4.1([6]). Let \(G = (V,E)\) be a graph. Then, \(\gamma_{all,2}^\infty(G) \leq \gamma(G)\).
In order to characterize the trees whose domination number is equal to their eternal distance-2 domination number we must first define the following family of trees and explore several properties of this family. We define the family of trees \(\mathcal{T}\) recursively as follows:
(a) Every tree with diameter at most 3 is in \(\mathcal{T}\), and
(b) If \(T \in \mathcal{T}\), then the tree \(T'\) formed by appending a star \(K_{1, m}\) with \(m \ge 2\) with an edge from a leaf of \(K_{1, m}\) to any vertex of \(T\) is also in \(\mathcal{T}\), and
(c) If \(T \in \mathcal{T}\) and \(v \in V(T)\) is a leaf such that there is a minimum dominating set containing \(v\), then for all trees \(T''\) formed by appending a star \(K_{1,m}\) where \(m \geq 1\) to \(v\) by adding an edge from \(v\) to the high degree vertex of the star, as well as appending \(t\geq 1\) leaves to \(v\), is also in \(\mathcal{T}\).
(d) If \(T \in \mathcal{T}\) and \(v \in V(T)\) is a leaf such that \(\gamma(T-v)=\gamma(T) – 1\), then \(T'''\) formed by appending two stars \(K_{1,m}\) and \(K_{1,M}\) where \(m,M\geq 1\) to \(v\) by adding an edge from \(v\) to the high degree vertex of the stars, is also in \(\mathcal{T}\).
Theorem 4.2. If \(T\) is a tree, then \(\gamma_{all, 2}^\infty(T) = \gamma(T)\) if and only if \(T \in \mathcal{T}\).
Proof. Suppose \(T \in \mathcal{T}\). If \(T\) has diameter at most 2, then \(T\) has a universal vertex, so \(\gamma_{all, 2}^\infty(T) = \gamma(T) = 1\). If \(T\) has diameter 3, then \(\gamma(T) = 2\) since \(T\) does not have a universal vertex, but the two non-leaves form a dominating set, and \(\gamma_{all, 2}^\infty(T) = 2\) by Lemma 3.4.
Suppose all trees \(S \in \mathcal{T}\) on fewer than \(n\) vertices satisfy \(\gamma_{all, 2}^\infty(S) = \gamma(S)\), and let \(T \in \mathcal{T}\) be a tree with \(n\) vertices and diameter at least 4. Suppose \(T\) is formed by appending \(K_{1, m}\), \(m\geq 2\), to some \(T' \in \mathcal{T}\). Then we have \(\gamma_{all, 2}^\infty(T) = \gamma_{all, 2}^\infty(T') + 1\) by Lemma 3.3. Moreover, \(\gamma(T) \le \gamma(T') + \gamma(K_{1, m}) = \gamma(T') + 1\), and any minimum dominating set of \(T\) contains either the stem of \(K_{1, m}\) or its unique leaf neighbour, which dominates no vertex of \(T'\), so \(\gamma(T') \le \gamma(T) – 1\). Therefore, \(\gamma(T) = \gamma(T') + 1\). Since \(\gamma_{all, 2}^\infty(T') = \gamma(T')\) by the induction hypothesis, it follows that \(\gamma_{all, 2}^\infty(T) = \gamma(T)\).
Now suppose \(T\) is formed from some \(T'' \in \mathcal{T}\) by taking a leaf \(v\) for which there is a minimum dominating set of \(T''\) containing \(v\), and appending to \(v\) a star \(K_{1,m}\) where \(m \geq 1\) by adding an edge to the high degree vertex of the star, as well as appending \(t\geq 1\) leaves. Then \(v \in V(T)\) is a \(2\)-leaf where \(T[L[v]]\) has diameter \(3\) and \(T'' = T – L(v)\). Then Lemma 3.3 implies \(\gamma_{all,2}^\infty(T) = \gamma_{all,2}^\infty(T'')+1\). Furthermore, let \(D\subset V(T'')\) be a minimum dominating set of \(T''\) where \(v \in D\). Then, \(D \cup \{u\}\) where \(u\) is the high degree vertex of the star appended to \(v\) in \(T\) is a dominating set of \(T\). This implies \(\gamma(T)\leq \gamma(T'')+1\). As \(T'' \in \mathcal{T}\) implies \(\gamma_{all,2}^\infty(T'') = \gamma(T'')\) and Lemma 4.1 implies \(\gamma(T'') +1 = \gamma_{all,2}^\infty(T'') +1 = \gamma_{all,2}^\infty(T) \leq \gamma(T)\) we conclude that \(\gamma(T)= \gamma(T'')+1\). Hence, \(\gamma_{all,2}^\infty(T) = \gamma(T)\) as required.
Finally, suppose \(T\) is formed by appending the high degree vertices in two stars \(K_{1,m}\) and \(K_{1,M}\) where \(m,M \geq 1\) to a leaf \(v\) in a tree \(T''' \in \mathcal{T}\) such that \(\gamma(T'''-v) = \gamma(T''')-1\). Then \(v\) is a \(2\)-leaf in \(T\) and Lemma 3.3 implies \(\gamma_{all,2}^\infty(T) = \gamma_{all,2}^\infty(T''')+1\). As \(\gamma(T'''-v) = \gamma(T''')-1\), all minimum dominating sets of \(T'''-v\) do not contain \(v\) or a neighbour of \(v\). Then, letting \(D\) be a minimum dominating set of \(T'''-v\) and letting \(u_1\) and \(u_2\) be the high degree vertices of the appended stars we see that \(D\cup \{u_1,u_2\}\) is a dominating set in \(T\), hence, \(\gamma(T) \leq \gamma(T'''-v)+2=\gamma(T''')+1\). It is easy to see that \(\gamma(T) \geq \gamma(T'''-v)+2=\gamma(T''')+1\) as \(T\) contains \(2\) leaves, call them \(w,x\), such that no vertex in \(N(w)\cup N(x)\) is in \(T'''\). Thus, \(\gamma(T) = \gamma(T''')+1\) implying \(\gamma(T) = \gamma_{all,2}^\infty(T)\) as required.
Conversely, suppose there exists a tree \(X\) such that \(X \notin \mathcal{T}\), but \(\gamma_{all, 2}^\infty(X) = \gamma(X)\). Let \(Y\) be a minimal such tree with respect to induced subgraphs. Then the diameter of \(Y\) is at least \(4\). It follows from Lemma 3.2 that there exists a \(2\)-leaf in \(Y\).
Suppose \(v \in V(Y)\) is a \(2\)-leaf such that \(Y[L[v]]\) has diameter \(2\), and let \(Y' = Y – L[v]\). By Lemma 3.3, we have \(\gamma_{all, 2}^\infty(Y) = \gamma_{all, 2}^\infty(Y') + 1\), and by Lemma 4.1, we have \(\gamma_{all, 2}^\infty(Y') \le \gamma(Y')\). Consider a leaf \(\ell \neq v\) in \(Y[L[v]]\). As \(v\) is a \(2\)-leaf and diameter of \(Y[L[v]]\) is \(2\), \(v\) is not adjacent to \(\ell\). Hence, any dominating set of \(Y\) contains a vertex in \(L(v)\) in order to guard \(\ell\). Thus \(\gamma(Y') < \gamma(Y)\). But this implies \(\gamma(Y)-1 = \gamma_{all,2}^\infty(Y)-1 = \gamma_{all,2}^\infty(Y') \leq \gamma(Y') \leq \gamma(Y)-1\). It follows that \(\gamma_{all, 2}^\infty(Y') = \gamma(Y')\). By the minimality of \(Y\), we have \(Y' \in \mathcal{T}\). But then by definition of \(\mathcal{T}\), we have \(Y \in \mathcal{T}\) by condition (2), a contradiction. Hence we may assume that for every \(2\)-leaf \(v\) in \(T\), the diameter of \(Y[L[v]]\) is at least \(3\).
Suppose \(v \in V(Y)\) is a 2-leaf such that \(Y[L[v]]\) has diameter at least 3, and let \(Y'' = Y – L(v)\). Observe \(v\) is a leaf in \(Y''\). By Lemma 3.3, we have \(\gamma_{all, 2}^\infty(Y) = \gamma_{all, 2}^\infty(Y'') + 1\), and by Lemma 4.1, we have \(\gamma_{all, 2}^\infty(Y'') \le \gamma(Y'')\). Let \(w\) and \(x\) be the ends of a longest path in \(Y[L[v]]\). Then \(x\) and \(w\) are leaves and \(3\leq \mathop{\mathrm{dist}}(w, x) \leq 4\). Then there is a minimum dominating set of \(Y\) that contains the unique neighbour of \(w\) and the unique neighbour of \(x\) both of which are members of \(N[v]\).
Suppose \(\mathop{\mathrm{dist}}(w,x)=3\) and assume without loss of generality that \(\mathop{\mathrm{dist}}(w, v) = 2\). Note that as \(\mathop{\mathrm{dist}}(w,x)=3\) and \(\mathop{\mathrm{dist}}(w, v) = 2\), \(v\) must be the neighbour of \(x\). Let \(D\) be such a minimum dominating set of \(Y\) containing \(v\) (the unique neighbour of \(x\)). It follows that the neighbour of \(w\) is not necessary to dominate any vertex in \(Y''\), so \(\gamma(Y'') < \gamma(Y)\). As before this implies that \(\gamma(Y)-1 = \gamma_{all,2}^\infty(Y)-1 = \gamma_{all,2}^\infty(Y'') \leq \gamma(Y'') \leq \gamma(Y)-1\), so \(\gamma(Y'') = \gamma(Y)-1\). Then \(D \setminus N(w)\) (which contains \(v\)) is a minimum dominating set of \(Y''\) and \(\gamma_{all,2}^\infty(Y'') = \gamma(Y'')\) and by the minimiality of \(Y\), \(Y'' \in \mathcal{T}\). But this implies \(Y \in \mathcal{T}\) by condition (3), a contradiction.
Suppose then that \(\mathop{\mathrm{dist}}(w,x)=4\). Then \(\mathop{\mathrm{dist}}(w,v)=\mathop{\mathrm{dist}}(x,v)= 2\). Let \(D\) be a minimum dominating set of \(Y\) containing the neighbour of \(w\) and \(x\), call them \(u_x,u_w\). Recall that
\[\begin{aligned} \gamma(Y)-1 = \gamma_{all,2}^\infty(Y)-1 = \gamma_{all,2}^\infty(Y'') \leq \gamma(Y''), \end{aligned}\] so \(\gamma(Y) \leq \gamma(Y'')+1\).
It follows that \(N(v) \cap L(v) = \{u_x,u_w\}\). Otherwise, there is a vertex \(z\) other than \(u_x\) or \(u_w\) in \(N(v) \cap L(v)\). Suppose such a \(z\) exists. Then, \(N[z] \cap D \neq \emptyset\). If the only neighbour of \(z\) in \(D\) is \(v\), \(D\setminus L(v)\) is a dominating set of \(Y''\) and \(|D\setminus L(v)| \leq \gamma(Y)-2\) implying \(\gamma(Y'')+2 \leq \gamma(Y)\). Otherwise, there is a neighbour of \(z\) other than \(v\) in \(D\). Then \(|D\cup L(v)| \geq 3\). Hence, \((D\cup \{v\})\setminus L(v)\) is a dominating set of size at most \(\gamma(Y)-2\) in \(Y''\), so again \(\gamma(Y'')+2 \leq \gamma(Y)\). But this is a contradiction, given we have shown, \(\gamma(Y'')+2 \leq \gamma(Y) \leq \gamma(Y'')+1\). We suppose then that \(N(v) \cap L(v) = \{u_x,u_w\}\).
Notice that as \(v\) is a leaf in \(Y''\) and \(N(v) \cap L(v) = \{u_x,u_w\}\subseteq D\) we can suppose without loss of generality that the neighbour of \(v\) in \(Y''\) is dominated by a vertex of \(D\) other than \(v\). Suppose just this. As we assume that the neighbour of \(v\) in \(Y''\) is dominated by a vertex of \(D\) other than \(v\), the set \(D\setminus\{u_x,u_w\}\) is a dominating set \(Y''-v\). Thus, \(\gamma(Y''-v)\leq \gamma(Y) – 2\). Additionally, \((D \cup \{v\}) \setminus \{u_x,u_w\}\) is clearly a dominating in \(Y''\). Hence, \(\gamma(Y'') \leq \gamma(Y)-1\). Again,
\[\begin{aligned} \gamma(Y)-1 = \gamma_{all,2}^\infty(Y)-1 = \gamma_{all,2}^\infty(Y'') \leq \gamma(Y'') \leq \gamma(Y)-1, \end{aligned}\] so we conclude \(\gamma(Y'') = \gamma(Y)-1\) implying that \(\gamma_{all,2}^\infty(Y'') = \gamma(Y'')\). By the minimiality of \(Y\) this implies \(Y''\in \mathcal{T}\).
Observe now that \(\gamma(Y'') \leq \gamma(Y''-v)+1\) as any dominating set of \(Y''-v\) union \(v\) dominated \(Y''\). Then
\[\begin{aligned} \gamma(Y'') – 1 \leq \gamma(Y''-v) \leq \gamma(Y)-2 = \gamma(Y'') – 1, \end{aligned}\] implying \(\gamma(Y''-v) = \gamma(Y'')-1\). Hence, \(v\) is a leaf in \(Y''\) such that \(\gamma(Y''-v) = \gamma(Y'')-1\) and \(v\) has exactly two neighbours in \(Y\) that are not in \(Y''\), \(u_x,u_w\), whose only neighbours other than \(v\) are leaves. Thus, \(Y\) can be obtained from \(Y''\) by condition (4). But this is a contradiction as \(Y \in \mathcal{T}\). This concludes the proof. ◻
We say a graph \(G\) is eternal distance-2 domination critical if deleting any non-cut vertex, \(v\), ensures that \(G-v\) has eternal distance-2 domination number strictly less than \(G\). Of course if \(T\) is a tree this is equivalent to stating that deleting any leaf from \(T\) reduces the eternal distance-2 domination number of \(T\). In this section we characterize which trees are eternally distance-2 domination critical. We begin with the following observation.
Lemma 5.1. If \(T = (V,E)\) is a tree and \(v \in V\) is a vertex adjacent to two leaves \(u,w\), then \(\gamma_{all,2}^\infty(T) = \gamma_{all,2}^\infty(T-u)\).
Proof. Suppose \(T = (V,E)\) is a tree and \(v \in V\) is a vertex adjacent to two leaves \(u,w\). Trivially, \(\gamma_{all,2}^\infty(T-u) \leq \gamma_{all,2}^\infty(T)\), hence it suffices to show \(\gamma_{all,2}^\infty(T-u) \geq \gamma_{all,2}^\infty(T)\). In order to show this, we describe how \(\gamma_{all,2}^\infty(T-u)\) guards can eternally dominates \(T\).
Let \(D\) be a minimum eternally dominating set in \(T-u\). Suppose \(\gamma_{all,2}^\infty(T-u)\) guards begin in multiset \(D\) in \(T\). If a vertex \(x \neq u\) is attacked, then the guards in \(T\) respond as if defending \(T-u\). If vertex \(u\) is attacked, then the guards move as if \(w\) were attacked in \(T-u\), except the guard \(g\) who would have moved (or remained on \(w\) if a guard already occupied \(w\)) to \(w\), instead \(g\) moves to \(u\). Notice that \(\mathop{\mathrm{dist}}(u,w) \leq 2\) and \(u\) and \(w\) share the same neighbours and second neighbours, so this strategy is always possible for the guards to execute given \(D\) was eternally dominating set in \(T-u\). Thus, \(\gamma_{all,2}^\infty(T-u) \geq \gamma_{all,2}^\infty(T)\) as required. ◻
Note that Lemma 5.1 implies that if \(T\) is eternal distance-2 domination critical, then every stem of \(T\) has exactly one leaf. Using this observation we are able to show the following result regarding the structure of \(2\)-leaves in an eternal distance-2 domination critical tree.
Lemma 5.2. If a tree \(T = (V,E)\) is eternal distance-2 domination critical, then for all \(2\)-leaves \(v\in V\), \(T[L[v]]\) is isomorphic to \(P_3\) or \(P_4\).
Proof. Suppose \(T = (V,E)\) is an eternal distance-2 domination critical tree and let \(v \in V\) be a \(2\)-leaf in \(T\). Suppose \(v\) is adjacent to multiple 1-leaves \(x_1, x_2\) with respective leaves \(y_1, y_2\). By Lemma 3.3, \(\gamma_{all, 2}^\infty(T) = \gamma_{all, 2}^\infty(T – L(v)) + 1\). Now, for \(T – y_2\), we have again by Lemma 3.3 that \(\gamma_{all, 2}^\infty(T – y_2) = \gamma_{all, 2}^\infty(T – L(v)) + 1\), since \((T – y_2)[L[v] \setminus\{y_2\}]\) has diameter at least 3. Thus \(\gamma_{all, 2}^\infty(T) = \gamma_{all, 2}^\infty(T – y_2)\), which contradicts \(T\) being eternal distance-2 domination critical. It follows, together with Lemma 5.1, that \(T[L[v]]\) is isomorphic to \(P_3\) or \(P_4\). ◻
In the following pair of results, we demonstrate that when these structured 2-leaves exist in an eternal distance-2 domination critical graph \(T\), then \(T\) must have been built from a smaller eternal distance-2 domination critical graph.
Lemma 5.3. Let \(T\) be a tree, and let \(T'\) be formed by appending a path on three vertices to a leaf of \(T\). Then \(T'\) is eternal distance-2 domination critical if and only if \(T\) is eternal distance-2 domination critical.
Proof. Let \(v\) be a leaf in both \(T\) and \(T'\). By Lemma 3.3, we have \(\gamma_{all, 2}^\infty(T') = \gamma_{all, 2}^\infty(T) + 1\) and \(\gamma_{all, 2}^\infty(T' – v) = \gamma_{all, 2}^\infty(T – v) + 1\). Thus \(\gamma_{all, 2}^\infty(T – v) < \gamma_{all, 2}^\infty(T)\) if and only if \(\gamma_{all, 2}^\infty(T' – v) < \gamma_{all, 2}^\infty(T')\).
Now, let \(\ell\) be the leaf of the appended path, and let \(x\) be the leaf of \(T\) to which the path was appended. By Lemma 3.3, we have \(\gamma_{all, 2}^\infty(T') = \gamma_{all, 2}^\infty(T) + 1\) and \(\gamma_{all, 2}^\infty(T' – \ell) = \gamma_{all, 2}^\infty(T – x) + 1\). Thus \(\gamma_{all, 2}^\infty(T – x) < \gamma_{all, 2}^\infty(T)\) if and only if \(\gamma_{all, 2}^\infty(T' – \ell) < \gamma_{all, 2}^\infty(T')\). Therefore, \(T'\) is eternal 2-domination critical if and only if \(T\) is eternal 2-domination critical. ◻
Lemma 5.4. Let \(T\) be a tree and let \(T'\) be formed by appending a path on two vertices and a single vertex to a leaf of \(T\). Then \(T'\) is eternal 2-domination critical if and only if \(T\) is eternal 2-domination critical.
Proof. Let \(T = (V,E)\) be a tree and let \(v \in V\) be a leaf in \(T\). Form \(T'\) by appending a path on two vertices and a single vertex to \(v\). Then Lemma 3.3 implies \(\gamma_{all,2}^\infty(T') = \gamma_{all,2}^\infty(T'-L(v)) + 1 = \gamma_{all,2}^\infty(T) + 1\) as \(T'-L(v) = T\). Let \(u\) be the leaf of \(T'\) resulting from the path of length \(2\) appended to \(v\) and let \(w\) be the lone vertex appended to \(v\).
Let \(x\) be a leaf in both \(T\) and \(T'\). By Lemma 3.3, we have \(\gamma_{all, 2}^\infty(T') = \gamma_{all, 2}^\infty(T) + 1\) and \(\gamma_{all, 2}^\infty(T' – x) = \gamma_{all, 2}^\infty(T – x) + 1\). Thus \(\gamma_{all, 2}^\infty(T – x) < \gamma_{all, 2}^\infty(T)\) if and only if \(\gamma_{all, 2}^\infty(T' – x) < \gamma_{all, 2}^\infty(T')\).
By Lemma 3.3, we have \(\gamma_{all, 2}^\infty(T') = \gamma_{all, 2}^\infty(T) + 1\) and \(\gamma_{all, 2}^\infty(T' – w) = \gamma_{all, 2}^\infty(T – v) + 1\). Thus \(\gamma_{all, 2}^\infty(T – v) < \gamma_{all, 2}^\infty(T)\) if and only if \(\gamma_{all, 2}^\infty(T' – w) < \gamma_{all, 2}^\infty(T')\).
Trivially, \(\gamma_{all, 2}^\infty(T' – u) \leq \gamma_{all, 2}^\infty(T-v)+1\) given \(T'[L[v]\setminus \{u\}]\) has diameter \(2\). Recall \(\gamma_{all,2}^\infty(T') = \gamma_{all,2}^\infty(T) + 1\) and assume that \(\gamma_{all, 2}^\infty(T – v) < \gamma_{all, 2}^\infty(T)\), then
\[\begin{aligned} \gamma_{all, 2}^\infty(T'-u) \leq \gamma_{all, 2}^\infty(T-v)+1 \leq \gamma_{all, 2}^\infty(T) = \gamma_{all, 2}^\infty(T') – 1, \end{aligned}\] implying \(\gamma_{all, 2}^\infty(T' – u) < \gamma_{all, 2}^\infty(T')\). So if \(T\) is eternal distance-2 domination critical, then \(T'\) is eternal distance-2 domination critical.
Suppose now that \(T'\) is eternal distance-2 domination critical but \(T\) is not. Then there exits a leaf \(z \in V\) such that \(\gamma_{all,2}^\infty(T-z) = \gamma_{all,2}^\infty(T)\). If \(z \neq v\), then we have already shown this leads to a contradiction given \(z\) will be a leaf in \(T\) and \(T'\).
If \(z = v\), then \(\gamma_{all,2}^\infty(T-v) = \gamma_{all,2}^\infty(T)\). By our assumption that \(T'\) is eternal distance-2 domination critical \(\gamma_{all,2}^\infty(T'-w) = \gamma_{all,2}^\infty(T')-1\) as \(T'\) requires more guards than \(T'-w\) and placing a guard on \(w\) then defending the rest of \(T'\) with \(\gamma_{all,2}^\infty(T'-w)\) guards is sufficient. Recall Lemma 3.3 implies \(\gamma_{all,2}^\infty(T'-w) = \gamma_{all,2}^\infty(T-v)+1\). Hence, \[\gamma_{all,2}^\infty(T') = \gamma_{all,2}^\infty(T'-w) + 1 = \gamma_{all,2}^\infty(T-v)+2 = \gamma_{all,2}^\infty(T)+2 ,\] contradicting Lemma 3.3 which implies \(\gamma_{all,2}^\infty(T') = \gamma_{all,2}^\infty(T)+1\). Thus, if \(T'\) is eternal distance-2 domination critical, then \(T\) is eternal distance-2 domination critical. This concludes the proof. ◻
The previous results allow us to provide a characterization of eternal distance-2 domination critical graphs.
Theorem 5.5. Let \(\mathcal{C}\) be the family of all trees \(T\) that can be obtained from the sequence \(T_1, \ldots, T_j\) of trees such that \(T_1\) is the single vertex tree \(K_1\) and \(T = T_j\), such that \(T_{i + 1}\) is the 1-sum of \(P_4\) and \(T_i\) at a leaf of \(T_i\) and any vertex of \(P_4\). If \(T\) is a tree, then \(T\) is eternal distance-2 domination critical if and only if \(T \in \mathcal{C}\).
Proof. Suppose \(T \in \mathcal{C}\). If \(T = K_1\), then \(T\) is trivially eternal distance-2 domination critical. If \(T = P_4\), we have \(\gamma_{all, 2}^\infty(P_4) = 2\) and \(\gamma_{all, 2}^\infty(P_3) = 1\) by Lemma 3.4, so \(T\) is eternal distance-2 domination critical.
Suppose all trees \(S \in \mathcal{C}\) on fewer than \(n\) vertices are eternal distance-2 domination critical, and let \(T \in \mathcal{C}\) be a tree with \(n\) vertices. Then \(T\) is the 1-sum of \(P_4\) and some \(T' \in \mathcal{C}\) at a leaf of \(T'\). It follows by Lemma 5.3 or Lemma 5.4 that \(T\) is eternal distance-2 domination critical.
Conversely, suppose there exists a tree \(X\) such that \(X \notin \mathcal{C}\) but \(X\) is eternally distance-2 domination critical. Let \(Y\) be a minimal such tree with respect to induced subgraphs. If the diameter of \(Y\) is at most 2, then by Lemma 3.4, \(\gamma_{all, 2}^\infty(T) = 1\), so \(Y = K_1\), and \(Y \in \mathcal{C}\), a contradiction. If the diameter of \(Y\) is 3, then Lemma 5.1 implies \(Y = P_4\), so \(Y \in \mathcal{C}\), a contradiction. Hence, we may assume \(Y\) has diameter at least 4. Therefore, by Lemma 3.2, \(Y\) has a 2-leaf \(v\), and by Lemma 5.2, \(Y[L[v]]\) is isomorphic to \(P_3\) or \(P_4\). It follows that \(Y\) is the 1-sum of \(P_4\) with some tree \(Z\). By Lemma 5.3 and Lemma 5.4, \(Z\) is eternal distance-2 domination critical, so by minimality of \(Y\), \(Z \in \mathcal{C}\). Hence, by construction, \(Y \in \mathcal{C}\), which is a contradiction, completing the proof. ◻
Recall the family \(\mathbb{T}\) introduced for Theorem 2.2. Perhaps surprisingly we will show that \(\mathbb{T}\) is also the class of graphs with \(\gamma_2(T) = \gamma_{all,2}^\infty(T)\). That is, there is no tree \(T\) such that \(\gamma_2(T) = \gamma_{all,2}^\infty(T)< \gamma(T)\). Equivalently \(\gamma_{all,2}^\infty(T) = \gamma_2(T)\) if and only if \(\gamma(T)= \gamma_2(T)\).
Theorem 6.1. Let \(T\) be a tree. Then \(\gamma_{all, 2}^\infty(T) = \gamma_2(T)\) if and only if \(T \in \mathbb{T}\).
Proof. If \(T\in \mathbb{T}\), then Theorem 2.2 implies \(\gamma(T) = \gamma_2(T)\). But \(\gamma_2(T) \leq \gamma_{all,2}^\infty(T)\) trivially while \(\gamma_{all,2}^\infty(T) \leq \gamma(T)\) by Lemma 4.1. Hence, \(\gamma(T) = \gamma_2(T)\) implies \(\gamma_2(T) = \gamma_{all,2}^\infty(T)\).
Let \(T\) be a tree with \(\gamma_{all, 2}^\infty(T) = \gamma_2(T)\). Let \(v_0, v_1, \ldots, v_k\) be a longest path in \(T\). If \(k \le 2\), then \(T\) is \(P_1\) or a star \(K_{1, m}\) for some non-negative integer \(m\), and clearly \(T\) is in \(\mathbb{T}\).
If \(k \in \{3, 4\}\), then \(\gamma_2(T) = 1\), but \(\gamma_{all, 2}^\infty(T) > 1\) by Lemma 3.4. Hence, we may assume \(k \ge 5\). We proceed by induction on the number \(n(T)\) of vertices of a tree \(T\) with \(\gamma_{all, 2}^\infty(T) = \gamma_2(T)\). It is easy to check that there is no graph on strictly less than \(6\) vertices with \(k\geq 5\) and \(\gamma_{all, 2}^\infty(T) = \gamma_2(T)\). Suppose then that \(n(T) \geq 6\). If \(n(T) = 6\), then \(T \cong P_6\) is the only tree with \(\gamma_{all, 2}^\infty(T) = \gamma_2(T)\) and \(P_6 \in \mathbb{T}\), by applying operation \(\mathbb{T}_3\) to \(P_2\). Now let \(T\) be a tree with \(\gamma_{all, 2}^\infty(T) = \gamma_2(T)\) and \(n(T) \ge 7\), and assume that each tree \(T'\) with \(n(T') < n(T)\), \(k \ge 5\), and \(\gamma_{all, 2}^\infty(T') = \gamma_2(T')\) is in \(\mathbb{T}\).
Suppose \(T\) contains a stem \(v\) with leaves \(x\) and \(y\). By Lemma 5.1, we have \(\gamma_{all, 2}^\infty(T) = \gamma_{all, 2}^\infty(T – x)\). It is also clear that any 2-dominating set of \(T – x\) also dominates \(T\). Thus \(\gamma_2(T) = \gamma_2(T – x)\). Therefore, \(\gamma_{all, 2}^{\infty}(T – x) = \gamma_2(T – x)\), so \(T – x \in \mathbb{T}\). But then \(T \in \mathbb{T}\) by Operation \(\mathbb{T}_1\), a contradiction. Thus, we may assume every stem of \(T\) has exactly one leaf.
As \(v_0\) must be a leaf, this implies \(\deg(v_1) = 2\), given \(v_1\) is a stem, and if \(v_1\) has a non-leaf neighbour \(w \neq v_2\), then \(v_0, v_1, \ldots, v_k\) is not a longest path in \(T\). Suppose \(\deg(v_2) > 2\). As \(v_0, v_1, \ldots, v_k\) is a longest path in \(T\) each neighbour of \(v_2\) distinct from \(v_3\) is a stem or leaf. Let \(x\) be a neighbour of \(v_2\) distinct from \(v_1,v_3\). Let \(D\) be the configuration of a minimum set of guards to eternally distance-2 dominate \(T\) after an attack on \(x\). Then in order to defend against a possible attack at \(v_0\), at least one of \(v_0, v_1, v_2 \in D\). Let \(D' = (D – L[v_2])\cap \{v_2\}\). Then \(|D'| < |D|\) as \(|D \cap L[v_2]| \geq 2\) given \(x \in L(v_2)\cap D\). But \(D'\) will be a distance 2-dominating set in \(T\), contradicting that \(\gamma_{all, 2}^\infty(T) = \gamma_2(T)\). Thus \(\deg(v_2) = 2\).
Suppose \(\deg(v_3) > 2\). Given \(k\geq 5\) if \(v_3\) is a stem in \(T\), then \(v_3\) has a leaf \(x\neq v_4\). Suppose \(v_3\) is a stem and \(x\) is a leaf incident to \(v_3\). Let \(D\) be the configuration of a minimum set of guards to eternally distance-2 dominate \(T\) after an attack on \(x\). Then in order to defend against a possible attack at \(v_0\), at least one of \(v_0, v_1, v_2 \in D\). Let \(D' = (D – L[v_2] – \{x\}) \cup \{v_2\}\). Then \(|D'| < |D|\) and \(D'\) distance-2 dominates \(T\), contradicting that \(\gamma_{all, 2}^\infty(T) = \gamma_2(T)\). Thus, \(v_3\) is not a stem of \(T\). Let \(T' = T – L[v_2]\). Since \(\deg_T(v_3) > 2\), \(v_3\) is not a leaf in \(T'\), and since \(k \ge 5\), \(v_3\) is not a stem in \(T'\). By Lemma 3.3, we have \(\gamma_{all, 2}^\infty(T) = \gamma_{all, 2}^\infty(T') + 1\), and trivially \(\gamma_2(T) \le \gamma_2(T') + 1\). Therefore, Proposition 2.1 implies, \[\gamma_2(T) \le \gamma_2(T') + 1 \le \gamma_{all, 2}^\infty(T') + 1 = \gamma_{all, 2}^\infty(T) = \gamma_2(T).\]
Thus, \(\gamma_2(T') = \gamma_{all, 2}^\infty(T')\) so by the induction hypothesis, \(T' \in \mathbb{T}\). Since \(T\) is obtained from \(T'\) by operation \(\mathbb{T}_2\), we conclude \(T \in \mathbb{T}\).
Thus, we assume \(\deg(v_3) = 2\). Let \(D\) be a configuration of a minimum set of guards to eternally distance-2 dominate \(T\) after an attack on \(v_3\). Then in order to defend against a possible attack at \(v_0\), at least one of \(v_0, v_1, v_2 \in D\). Let \(D' = (D – \{v_0,v_1,v_2,v_3\}) \cup \{v_2\}\). Then, \(|D'|<|D|\). Given, \(|D'| < |D|\), it must be true that \(D'\) is not a distance-2 dominating set of \(T\). Thus \(v_3 \in D\) and \(v_4\) has a neighbour, say \(u\), that is not distance-2 dominated by \(D'\). As \(D-\{v_0,v_1,v_2,v_3\} = D' – \{v_0,v_1,v_2,v_3\}\) this implies \(v_3\) is the unique vertex in \(D\) with distance at most \(2\) from \(u\).
Consider the components of \(T – u\). Each component can be eternally distance-2 dominated by its vertices in \(D\), since no vertex of \(D\) except \(v_3\) is within distance \(2\) of \(u\). If \(\deg(u) > 1\), then let \(z \neq v_4\) be a neighbour of \(u\), and let \(\hat{D}\) be the configuration of the guards after an attack on \(z\), starting from the configuration \(D\). It is clear that the guard which defends the attack at \(z\) must be in a component of \(T-u\) distinct from \(v_4\), given \(T\) is a tree. Let \(\hat{D}_u = \hat{D}\).
Then for all non-leaf neighbours of \(v_4\) that are not distance-2 dominated in \(D'\), \(u_1,\dots, u_l\), we can define sets \(\hat{D}_{u_i}\) as above. Furthermore, as each attack on a vertex \(z_i = z\) (given \(u_i = u\)) calls for a distinct set of guards \(g_i\) to defend against it, there is a eternally distance-2 dominating set \(\mathcal{D}\) given by all guards \(g_i\) defending against attacks at \(z_i\), for all \(1 \leq i \leq l\), while the rest of the guards in \(D\) do not move. Then \(\mathcal{D}' = (\mathcal{D} – \{v_0,v_1,v_2,v_3\}) \cup \{v_2\}\) is a distance-2 dominating set of \(T\), given all vertices of the \(2\)-neighbourhood of \(v_3\) are dominated, and \(|\mathcal{D}'| < |\mathcal{D}|\), contradicting that \(\gamma_{all, 2}^\infty(T) = \gamma_2(T)\). Hence all neighbours of \(v_4\) are leaves in \(T\).
Then \(v_5\) is a leaf. This implies \(T\) is \(P_6\) written \(v_0, v_1, v_2,v_3,v_4, v_5\) with potentially extra leaves appended \(v_4\). Notice that \(P_6 \in \mathbb{T}\) given we can form \(P_6\) by applying operation \(\mathbb{T}_3\) to \(P_2\). If \(T\) is not \(P_6\), then we can obtain \(T\) from \(P_6\) via (potentially) repeated applications of \(\mathbb{T}_1\). Thus, \(T \in \mathbb{T}\). This concludes the proof. ◻
Motivated by a question posed in [6], we explore the extreme values the eternal distance-\(k\) domination number can take in trees. We begin by giving a general upper bound for the eternal distance-\(k\) domination number of trees. As the eternal distance-\(k\) domination number of a graph is upper bounded by the eternal distance-\(k\) domination number of its spanning subgraphs, this implies a general upper bound for connected graphs. Note this generalises a result of Chambers, Kinnersley, and Prince [4]. Beyond this we construct a family of trees which meet this upper bound, as well as a family of trees which has eternal domination number at most \(\frac{2n}{1+ \sum\limits_{i=1}^k\Delta(\Delta-1)^{i-1}}\), which is the twice the lowest possible value the distance-\(k\) domination number of a connected graph can take.
Theorem 7.1. If \(G\) is a connected graph of order \(n\), then \[\frac{n}{1+ \sum\limits_{i=1}^k\Delta(\Delta-1)^{i-1}} \leq \gamma_{all,k}^\infty(G) \leq \left \lceil \frac{n}{k+1} \right \rceil.\]
Proof. The lower bound is trivial as each vertex can distance-\(k\) dominate at most \(1+ \sum\limits_{i=1}^k\Delta(\Delta-1)^{i-1}\) vertices. So \(\gamma_{all,k}^\infty(G) \geq \gamma_k(G) \geq \frac{n}{1+ \sum\limits_{i=1}^k\Delta(\Delta-1)^{i-1}}\). It remains to be shown that \(\gamma_{all,k}^\infty(G) \leq \left \lceil \frac{n}{k+1} \right \rceil\).
As deleting edges will never help the guards defend the graph it is sufficient to prove the result for trees. Suppose then that \(G = T = (V,E)\) is a tree. When the diameter of \(T\) is strictly less than \(2k\) the result follows by Lemma 3.4. Otherwise, the diameter of \(T\) is at least \(2k\), in which case Lemma 3.2 implies that there exists a \(k\)-leaf \(v \in V\).
Suppose \(T\) is a smallest counterexample. Then the diameter of \(T\) is at least \(2k\). Let \(v \in V\) be a \(k\)-leaf in \(T\) and let \(T'=T – L[v]\) when the diameter of \(T[L[v]]\) is \(k\), and \(T'=T – L(v)\) otherwise. By the definition of a \(k\)-leaf this implies \(|V(T')|\leq n-(k+1)\). By the minimality of \(T\), \(T'\) is not a counterexample, hence, \[\gamma_{all,k}^\infty(T') \leq \left \lceil \frac{n-(k+1)}{k+1} \right \rceil = \left \lceil \frac{n}{k+1} \right \rceil – 1.\]
Let \(\gamma_{all,k}^\infty(T')\) guards defend the subgraph \(T'\) of \(T\) and place a single guard on \(v\). Note that this will be at most \(\left \lceil \frac{n}{k+1} \right \rceil\) guards.
If the diameter \(T[L[v]]\) is \(k\), then the guard at \(v\) can protect \(L[v]\) indefinitely while the \(\gamma_{all,k}^\infty(T')\) guards protect \(T'\) indefinitely. Otherwise, the diameter \(T[L[v]]\) is at least \(k+1\). In this case, let the guards proceed by the same strategy described in case 2 of the proof of Lemma 3.3. This strategy will protect \(T\) indefinitely. Thus, \[\gamma_{all,k}^\infty(T) \leq \gamma_{all,k}^\infty(T') +1 \leq \left \lceil \frac{n}{k+1} \right \rceil,\] which concludes the proof. ◻
Note that [6] showed that paths are a family of graphs that meet the upper bound of Theorem 7.1. The reason for this is because in any distance-\(k\) dominating set we must maintain guards within distance \(k\) of each leaf, therefore to protect against attacks on leaves these guards can never leave the \(k\) neighbourhood of each leaf. Hence, more guards are required to protect vertices which are distance slightly more than \(k\) from a leaf. By induction this will force paths to require the maximum possible number of guards.
Using a similar ideas we construct a large family \(\mathcal{T}_{M,k}\) of trees which also have eternal distance-\(k\) domination number \(\left \lceil \frac{n}{k+1} \right \rceil\). We define \(\mathcal{T}_{M,k}\) as follows. Let \(T'\) be any tree, construct \(T \in \mathcal{T}_{M,k}\) by connecting a path \(P_v = v_1 \dots v_{k}\) to each vertex \(v \in V(T')\). That is for each \(v\) add an edge \((v,v_1)\) so that \(P_v\) becomes part of \(T\).
Theorem 7.2. If \(T \in \mathcal{T}_{M,k}\), then \(\gamma_{all,k}^\infty(T) = \left \lceil \frac{n}{k+1} \right \rceil\).
Proof. Let \(T = (V,E) \in \mathcal{T}_{M,k}\), then \(T\) is given by appending paths of length \(k\) to each vertex in some other tree \(T'\). Notice that \(|V| = n =(k+1)|V(T')|\). We aim to show that \(\gamma_{all,k}^\infty(T) = |V(T')|\). By Theorem 7.1, \(\gamma_{all,k}^\infty(T) \leq |V(T')|\) so all that remains to be shown is that \(\gamma_{all,k}^\infty(T) \geq |V(T')|\).
Note that in each distance-\(k\) dominating set of \(T\) for each path \(P_v\) in \(T\) appended to a vertex \(v \in V(T')\) there must be at least \(1\) guard in \(P_v\cup \{v\}\) to distance-\(k\) dominate the leaf at the end of \(P_v\). As for each \(u\neq v \in V(T')\), \((P_v \cup \{v\})\cap (P_u \cup \{u\}) = \emptyset\) this implies \(\gamma_k(T) \geq |V(T')|\). Hence, \(\gamma_{all,k}^\infty(T) \geq \gamma_k(T) \geq |V(T')|\) as required. This completes the proof. ◻
Now we construct a family of trees \(\mathcal{T}_{m,k, \Delta}\) which all have eternal distance-\(k\) domination number at most \(\frac{2n}{1+ \sum\limits_{i=1}^k\Delta(\Delta-1)^{i-1}}\). Let \(T_{k,\Delta}\) be the complete \((\Delta-1)\)-ary tree of depth \(k\) except the root vertex has \(\Delta\) followers rather than \(\Delta-1\). Let \(T_{k,\Delta} \in \mathcal{T}_{m,k, \Delta}\), we complete out definition of \(\mathcal{T}_{m,k, \Delta}\) as follows; for any \(T_1,T_2 \in \mathcal{T}_{m,k, \Delta}\) let \(T_3\) be any tree formed by adding an edge between two vertices of \(T_1\) and \(T_2\) which have degree strictly less than \(\Delta\), then \(T_3 \in \mathcal{T}_{m,k, \Delta}\). Notice that like \(\mathcal{T}_{M,k}\), \(\mathcal{T}_{m,k,\Delta}\) contains arbitrarily many vertices of high degree.
Theorem 7.3. If \(T \in \mathcal{T}_{m,k,\Delta}\), then \[\gamma_{all,k}^\infty(T) \leq \frac{2n}{1+ \sum\limits_{i=1}^k\Delta(\Delta-1)^{i-1}}.\]
Proof.Let \(T = (V,E) \in \mathcal{T}_{m,k,\Delta}\). We aim to show \(\gamma_{all,k}^\infty(T) \leq \frac{2n}{1+ \sum\limits_{i=1}^k\Delta(\Delta-1)^{i-1}}\). Note that if \(T = T_{k,\Delta}\), then the result follows from Lemma 3.4. Suppose then that \(T \neq T_{k,\Delta}\) is a smallest counterexample.
By the definition of \(\mathcal{T}_{m,k,\Delta}\), there exists an edge \(e \in E\) such that \(T-e\) is a graph with two connected components \(T_1\) and \(T_2\) each of which is \(\mathcal{T}_{m,k,\Delta}\). As \(T\) is a smallest counterexample, \(T_1\) and \(T_2\) are not counterexamples. Thus, if \(|V(T_1)| = a\) and \(|V(T_1)| = b\), we know \(n = a+b\) and \(\gamma_{all,k}^{\infty}(T_1) = \frac{2a}{1+ \sum\limits_{i=1}^k\Delta(\Delta-1)^{i-1}}\) and \(\gamma_{all,k}^{\infty}(T_2) = \frac{2b}{1+ \sum\limits_{i=1}^k\Delta(\Delta-1)^{i-1}}\).
It is not hard to see that if as \(V = V(T_1)\cup V(T_2)\) and \(T_1\), \(T_2\) are subgraphs of \(T\), \[\begin{aligned} \gamma_{all,k}^{\infty}(T) &\leq \gamma_{all,k}^{\infty}(T_1) + \gamma_{all,k}^{\infty}(T_2) \\ &= \frac{2a}{1+ \sum\limits_{i=1}^k\Delta(\Delta-1)^{i-1}}+\frac{2b}{1+ \sum\limits_{i=1}^k\Delta(\Delta-1)^{i-1}} \\ &= \frac{2n}{1+ \sum\limits_{i=1}^k\Delta(\Delta-1)^{i-1}}, \end{aligned}\] this completes the proof. ◻
We have resolved a number of questions regarding the eternal distance-2 domination number of trees, in particular several questions raised in [6]. We do this by giving a polynomial time algorithm (Theorem 3.5) for calculating the eternal distance-2 domination of a tree, then using the reductions involved in this algorithm we characterize which trees have domination number equal to their eternal distance-2 domination number (Theorem 4.2). Beyond this we characterize which trees are eternal distance-2 domination critical (Theorem 5.5) and which trees have eternal distance-2 domination number equal to their distance-2 domination number (Theorem 6.1). These results are similar to work by Klostermeyer and MacGillivray [12] who proved several characterizations for trees in the context of eternal domination.
Additionally, we generalize upper bounds on the eternal domination number given by Chambers, Kinnersley, and Prince [4] to the eternal distance-\(k\) domination number. We also give a lower bound for the eternal distance-\(k\) domination number in terms of order and maximum degree. To demonstrate that the upper bound we prove is tight we construct an infinite family of trees whose eternal distance-\(k\) domination number meets our upper bound. We conclude the paper by listing several open problems and conjectures.
The first of these conjectures arise from our observation that eternal distance-\(k\) domination seems to have some fundamental differences in the \(k \leq 2\) and \(k>2\) cases. This is highlighted by the effectiveness of Lemma 3.3 for \(k \leq 2\) and subsequent failure for \(k >2\).
Conjecture 8.1. For all integers \(k>2\), determining \(\gamma_{all,k}^\infty(T)\) where \(T\) is a tree is polynomial time bounded by a polynomial \(p(n)\) independent of \(k\).
Next we observe that Theorem 6.1 combined with work in [17] implies that if \(\gamma_2(T) = \gamma_{all,2}^\infty(T)\), then \(\gamma_{all,2}^\infty(T) = \gamma(T)\). We conjecture ’ that a similar result holds for \(k>2\). Recall that \(\gamma_k \leq \gamma_{all,k}^\infty \leq \gamma_{\left \lfloor \frac{k}{2} \right \rfloor}\) for all graphs.
Conjecture 8.2. For all \(k>2\) and trees \(T\), if \(\gamma_k(T) = \gamma_{all,k}^\infty(T)\), then \(\gamma_{all,k}^\infty(T) = \gamma_{\left \lfloor \frac{k}{2} \right \rfloor} (T)\).
The following are several questions which merit study in future work as they are natural to consider yet outside the scope of this paper.
Question 8.3. What is the maximum \(m\) as a function of \(n\), so that there exists a graph on \(n\) vertices and \(m\) edges with eternal distance-\(k\) domination number \(\left \lceil \frac{n}{k+1} \right \rceil\).
Question 8.4. For fixed integers \(k,t,\) and \(n\) where \(t>k+1\) what is the smallest integer \(m\) such that for all graphs \(G\) with order \(n\) and size \(m\), \(\gamma_{all,k}^\infty(G) \leq \frac{n}{t}\)?
Question 8.5. Let \(k,t \geq 1\) be distinct positive integer. Does there exist a family of graphs \(\mathcal{G}\) where determining \(\gamma_{all,k}^\infty(G)\) is polynomial time for graphs in \(\mathcal{G}\), but determining \(\gamma_{all,t}^\infty(G)\) is not polynomial time for graphs in \(\mathcal{G}\)? If so which families exhibit this dichotomy?
We would like to acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) through the Canadian Graduate Scholarship – Master’s program. We are grateful to the anonymous reviewers for their helpful comments, which increased the quality of this paper.