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 three.

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 (2015b), 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 (1995), ReVelle (1997), ReVelle & Rossing (1999), and Stewart (1999), the eternal domination problem was initially described in 2004 in a paper by Burger, Cockayne & Grundlingh (2004). That was followed by the publication of a paper on eternal domination by Goddard, Hedetniemi & Hedetniemi (2005), 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, Hededtniemi & Hedetniemi (2005) 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 (2015b).

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 & Brigham (2007)). 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 (2007) that the eternal domination number of a graph with independence number α is a most α(α + 1)/2. Goldwasser & Klostermeyer (2008) 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 & Slater 1998a), 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 & Prince (2006), see also Klostermeyer & Mynhardt (2015b).

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 & Slater (1998a) and Goncalves, Pinlou & Rao (2011). The m-eternal domination number in grid graphs was first studied in Goldwasser, Klostermeyer & Mynhardt (2013) 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 & van Bommel (2015) to

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

when n ≥ 11. This bound was subsequently slightly improved in Messinger & Delaney (2015) in some cases.

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

Braga, de Souza & Lee (2015a) proved that γ^m_∞ = α for all proper interval graphs and the same authors also proved, see Braga, de Souza & Lee (2015b), 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, Hededtniemi & Hedetniemi (2005).

Open questions

According to Klostermeyer & Mynhardt (2015b), 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 (2015a) 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

\gamma _{\infty }(G\,\Box \,H)\geq \gamma _{\infty }(G)\gamma _{\infty }(H).

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 (2015a).

Two fundamental open questions on eternal domination are listed by Douglas West at . 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 (2015b), 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 .

Arquilla, H.; Frederickson, H. (1995), "Graphing an optimal grand strategy", Military Operations Research, 1: 3–17, doi:10.5711/morj.1.3.3 .

Beaton, I.; Finow, 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. (2015a), "The eternal dominating set problem for proper interval graphs", Information Processing Letters, to appear: 582–587, doi:10.1016/j.ipl.2015.02.004 .

Braga, A.; de Souza, C.; Lee, O. (2015b), "A note on the paper "Eternal security in graphs" by Goddard, Hedetniemi, and Hedetniemi (2005)", to appear .

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.; Kinnnersly, B.; Prince, N. (2006), "Mobile eternal security in graphs", Unpublished manuscript .

Finbow, S.; Messinger, M-E.; van Bommel, M. (2015), "Eternal domination in 3 x n grids", Australas. J. Combin., 61: 156–174 .

Goldwasser, J.; Klostermeyer, W. (2008), "Tight bounds for eternal dominating sets in graphs", Discrete Math., 308: 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 of Discrete Mathematics, 25: 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 .

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, to appear: 283, doi:10.7151/dmgt.1799 .

Klostermeyer, W.; Mynhardt, C. (2015b), Protecting a graph with mobile guards, p. 21, arXiv:1407.5228, 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", graduate thesis, Rheinischen Friedrich-Wilhlems University, Bonn, Germany .

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: 585–594, doi:10.2307/2589113 .

Stewart, I. (1999), "Defend the Roman Empire!", Scientific American, 281: 136–138, doi:10.1038/scientificamerican1299-136 .

van Bommel, C.; van Bommel, M., "Eternal domination number of 5 x n grids", J. Combin. Math. Combin. Comput, to appear .

This article is issued from Wikipedia - version of the 12/2/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.