In graph theory, an eternal dominating set for a graphG = is a subsetD of V such that D is a dominating set on which mobile guards are initially located. The set D must be such that for any infinite sequence of attacks occurring sequentially at vertices, the set D can be modified by moving a guard from an adjacent vertex to the attacked vertex, provided the attacked vertex has no guard on it at the time it is attacked. The configuration of guards after each attack must induce a dominating set. The eternal domination number, γ∞, is the minimum number of vertices possible in the initial set D. For example, the eternal domination number of the cycle on five vertices is two. The eternal dominating set problem, also known as the eternal domination problem and the eternal security problem, can also be interpreted as a combinatorial game played between two players that alternate turns: a defender, who chooses the initial dominating set D and the guard to send to each attack that occurs at a vertex without a guard; and an attacker, who chooses the vertex to be attacked on their turn. The attacker wins the game if they can ever choose a vertex to be attacked such that there is no guard on that vertex or a neighboring vertex; the defender wins otherwise. In other words, the attacker wins the game if they can ever attack a vertex such that the attack cannot be defended. As noted in , the eternal dominating set problem is related to the k-server problem in computer science.
History
Motivated by ancient problems in military defense described in the series of papers,,, and, the eternal domination problem was initially described in 2004 in a paper by. That was followed by the publication of a paper on eternal domination by, which also introduced a variation on the problem called m-eternal domination in which all of the guards are allowed to move to adjacent vertices, if they so desire, in response to an attack, so long as one guard moves to the attacked vertex. Subsequent to the paper, a number of papers by other authors appeared in the mathematical literature. In these subsequent papers, several additional variations on the eternal domination problem were proposed including the eternal vertex cover problem, the eternal independent set problem, eternal total dominating sets, eternal connected dominating sets, and eternal dominating sets in the eviction model. A survey paper describing many of the results on the eternal domination problem and many of the variations of the problem can be found at.
Bounds
Let G be a graph with n ≥ 1 vertices. Trivially, the eternal domination number is at least the domination number γ. In their paper, Goddard, Hedetniemi, and Hedetniemi proved the eternal domination number is at least the independence number of G and at most the clique covering number of G. Therefore, the eternal domination number of G is equal to the clique covering number of G for all perfect graphs, due to the perfect graph theorem. It has been shown that the eternal domination number of G is equal to the clique covering number of G for several other classes of graph, such as circular-arc graphs and series-parallel graphs. Goddard, Hedetniemi, and Hedetniemi also demonstrated a graph in which the eternal domination number of the graph is less than the clique covering number. It was proven by that the eternal domination number of a graph with independence number α is a most α/2. proved that there are infinitely many graphs where the eternal domination number is exactly α/2.
Bounds on the ''m''-eternal domination number
Goddard, Hedetniemi, and Hedetniemi proved the m-eternal domination number, denoted γm∞, is at most the independence number of G. Hence, the eternal domination parameters fit nicely into the famous domination chain of parameters, see, as follows: where θ denotes the clique-covering number of G and γ∞ denotes the eternal domination number. An upper bound of ⌈n/2⌉ on γm∞ for graphs with n vertices was proven in, see also. The m-eternal domination number in grid graphs has attracted attention, inspired by attention given to the domination number of grid graphs, see and. The m-eternal domination number in grid graphs was first studied in where it was shown that and The latter was improved in to when n ≥ 11. This bound was subsequently slightly improved in in some cases. Finally, the bounds were closed in, where it was shown that The cases for 4 by and grids and 5 by n grids were considered in and, respectively. proved that γm∞ = α for all proper interval graphs and the same authors also proved, see, that there exists a Cayley graph for which the m-eternal domination number does not equal the domination number, contrary to the claim in.
Open questions
According to, one of the main unsolved questions is the following: Does there exist a graph G such that γ equals the eternal domination number of G and γ is less than the clique covering number of G? proved that any such graph must contain triangles and must have maximum vertex degree at least four. Similar to Vizing's conjecture for dominating sets, it is not known whether for all graphs G and H The analogous bound is known not to hold for all graphs G and H for the m-eternal domination problem, as shown in. Two fundamental open questions on eternal domination are listed by Douglas West at . Namely, whether γ∞ equals the clique covering number for all planar graphs G and whether γ∞ can bounded below by the Lovász number, also known as the Lovász theta function.
A number of other open questions are stated in the survey paper, including many questions on the variations of eternal dominating sets mentioned above.
