Eternal dominating set

In graph theory, an eternal dominating set for a graph G = (V, E) is a subset D of V such that D is a dominating set on which mobile guards are initially located (at most one guard may be located on any vertex). 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, γ_∞(G), 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 (Klostermeyer Mynhardt), 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 (Arquilla Fredricksen), (ReVelle Rosing), and (Stewart 1999), the eternal domination problem was initially described in 2004 in a paper by (Burger Cockayne). That was followed by the publication of a paper on eternal domination by (Goddard Hedetniemi), 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 (assuming there was not a guard on the attacked vertex, otherwise no guard needs to move). Subsequent to the (Goddard Hedetniemi) 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 (the latter model requires that when attacks occur a vertex with a guard and the guard must move to a neighboring vertex that contains no guard, if one exists). 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 (Klostermeyer Mynhardt).

Bounds

Let G be a graph with n ≥ 1 vertices. Trivially, the eternal domination number is at least the domination number γ(G). 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 (the clique covering number of G is equal to the chromatic number of the complement 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 (as proven in (Regan 2007)) and series-parallel graphs (as proven in (Anderson Barrientos)). 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 (Klostermeyer MacGillivray) that the eternal domination number of a graph with independence number α is a most α(α + 1)/2. (Goldwasser Klostermeyer) proved that there are infinitely many graphs where the eternal domination number is exactly α(α + 1)/2.

Bounds on the m-eternal domination number

Goddard, Hedetniemi, and Hedetniemi proved the m-eternal domination number, denoted γ^m_∞(G), is at most the independence number of G. Hence, the eternal domination parameters fit nicely into the famous domination chain of parameters, see (Haynes Hedetniemi), as follows:

γ(G) ≤ γ^m_∞(G) ≤ α(G) ≤ γ_∞(G) ≤ θ(G)

where θ(G) denotes the clique-covering number of G and γ_∞(G) denotes the eternal domination number.

An upper bound of ⌈n/2⌉ on γ^m_∞(G) for graphs with n vertices was proven in (Chambers Kinnersly), see also (Klostermeyer Mynhardt).

The m-eternal domination number in grid graphs has attracted attention, inspired by attention given to the domination number of grid graphs, see (Haynes Hedetniemi) and (Goncalves Pinlou). The m-eternal domination number in grid graphs was first studied in (Goldwasser Klostermeyer) where it was shown that

γ^m_∞ = ⌈2n/3⌉ for the 2 by n grid with n ≥ 2

and

γ^m_∞ ≤ ⌈8n/9⌉ for 3 by n grids.

The latter was improved in (Finbow Messinger) to

1 + ⌈4n/5⌉ ≤ γ^m_∞ ≤ 2 + ⌈4n/5⌉

when n ≥ 11. This bound was subsequently slightly improved in (Messinger Delaney) in some cases. Finally, the bounds were closed in (Finbow van Bommel), where it was shown that

γ^m_∞ = ⌈(4n+7)/5⌉ for n ≥ 22.

The cases for 4 by and grids and 5 by n grids were considered in (Beaton Finbow) and (van Bommel van Bommel), respectively.

(Braga de Souza) proved that γ^m_∞ = α for all proper interval graphs and the same authors also proved, see (Braga de Souza), that there exists a Cayley graph for which the m-eternal domination number does not equal the domination number, contrary to the claim in (Goddard Hedetniemi).

Open questions

According to (Klostermeyer Mynhardt), one of the main unsolved questions is the following: Does there exist a graph G such that γ(G) equals the eternal domination number of G and γ(G) is less than the clique covering number of G? (Klostermeyer Mynhardt) 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

[math]\displaystyle{ \gamma_\infty(G\,\Box\,H) \ge \gamma_\infty(G)\gamma_\infty(H). }[/math]

The analogous bound is known not to hold for all graphs G and H for the m-eternal domination problem, as shown in (Klostermeyer Mynhardt).

Two fundamental open questions on eternal domination are listed by Douglas West at [1]. Namely, whether γ_∞(G) equals the clique covering number for all planar graphs G and whether γ_∞(G) 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 (Klostermeyer Mynhardt), including many questions on the variations of eternal dominating sets mentioned above.

References

• Anderson, M.; Barrientos, C.; Brigham, R.; Carrington, J.; Vitray, R.; Yellen, J. (2007), "Maximum demand graphs for eternal security", J. Combin. Math. Combin. Comput. 61: 111–128, https://www.researchgate.net/publication/265463450 .
• Arquilla, H.; Fredricksen, H. (1995), "Graphing an optimal grand strategy", Military Operations Research 1 (3): 3–17, doi:10.5711/morj.1.3.3 .
• Beaton, I.; Finbow, S.; MacDonald, J. (2013), "Eternal domination set problem of grids", J. Combin. Math. Combin. Comput. 85: 33–38 .
• Braga, A.; de Souza, C.; Lee, O. (2015), "The eternal dominating set problem for proper interval graphs", Information Processing Letters 115 (6–8): 582–587, doi:10.1016/j.ipl.2015.02.004 .
• Braga, A.; de Souza, C.; Lee, O. (2016), "A note on the paper "Eternal security in graphs" by Goddard, Hedetniemi, and Hedetniemi (2005)", Journal of Combinatorial Mathematics and Combinatorial Computing 96: 13–22 .
• Burger, A.P.; Cockayne, E.J.; Grundlingh, W.R.; Mynhardt, C.M.; van Vuuren, J.; Winterbach, W. (2004), "Infinite order domination in graphs", J. Combin. Math. Combin. Comput. 50: 179–194 .
• Chambers, E.; Kinnersly, B.; Prince, N. (2006), "Mobile eternal security in graphs", Unpublished Manuscript, http://staff.imsa.edu/~nprince/researchfiles/MES.ps, retrieved 2015-02-21 .
• Finbow, S.; Messinger, M-E.; van Bommel, M. (2015), "Eternal domination in 3 x n grids", Australas. J. Combin. 61: 156–174 .
• Finbow, S.; van Bommel, M.F. (2020), "The eternal domination number for 3 x n grid graphs", Australas. J. Combin. 71: 1–23 .
• Goddard, Wayne; Hedetniemi, Sandra M.; Hedetniemi, Stephen T. (January 2005). "Eternal Security in Graphs". Journal of Combinatorial Mathematics and Combinatorial Computing 52. https://www.researchgate.net/publication/249799004_Eternal_Security_in_Graphs. 
• Goldwasser, J.; Klostermeyer, W. (2008), "Tight bounds for eternal dominating sets in graphs", Discrete Math. 308 (12): 2589–2593, doi:10.1016/j.disc.2007.06.005 .
• Goldwasser, J.; Klostermeyer, W.; Mynhardt, C. (2013), "Eternal protection in grid graphs", Utilitas Math. 91: 47–64 .
• Goncalves, D.; Pinlou, A.; Rao, M.; Thomasse, S. (2011), "The domination number of grids", SIAM Journal on Discrete Mathematics 25 (3): 1443–1453, doi:10.1137/11082574 .
• Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998a), Fundamentals of Domination in Graphs, Marcel Dekker, ISBN 0-8247-0033-3, OCLC 37903553, https://archive.org/details/fundamentalsofdo0000hayn .
• Klostermeyer, W.; MacGillivray, G. (2007), "Eternal security in graphs of fixed independence number", J. Combin. Math. Combin. Comput. 63: 97–101 .
• Klostermeyer, W.; Mynhardt, C. (2015a), "Domination, Eternal Domination, and Clique Covering", Discuss. Math. Graph Theory 35 (2): 283, doi:10.7151/dmgt.1799 .
• Klostermeyer, W.; Mynhardt, C. (2015b), "Protecting a graph with mobile guards", Applicable Analysis and Discrete Mathematics 10: 21, doi:10.2298/aadm151109021k .
• Messinger, M-E.; Delaney, A. (2015), Closing the gap: Eternal domination on 3 x n grids .
• Regan, F. (2007), Dynamic variants of domination and independence in graphs, Rheinischen Friedrich-Wilhlems University .
• ReVelle, C. (2007), "Can you protect the Roman Empire?", Johns Hopkins Magazine 2 .
• ReVelle, C.; Rosing, K. (2000), "Defendens Imperium Romanum: A classical problem in military strategy", Amer. Math. Monthly 107 (7): 585–594, doi:10.2307/2589113 .
• Stewart, I. (1999), "Defend the Roman Empire!", Scientific American 281 (6): 136–138, doi:10.1038/scientificamerican1299-136, Bibcode: 1999SciAm.281f.136S .
• van Bommel, C.; van Bommel, M. (2016), "Eternal domination number of 5 x n grids", J. Combin. Math. Combin. Comput 97: 83-102 .