Originator(s): W. Goddard, S.M Hedetniemi, S.T. Hedetniemi (communicated by Klostermeyer - REGS 2008)
Definitions: A dominating set in a graph G is a set S such that every vertex outside S has a neighbor in S; the minimum size of such a set is the domination number. View the vertices of a dominating set S as locations of protecting armies; when a vertex v not in S is attacked, the army at a vertex of S adjacent to v can move to v to defeat the attack. An eternal dominating or eternally secure set is a dominating set that permits eternal defense in the following sense: when a vertex not in the current dominating set is attacked, moving the army from some adjacent vertex in the current dominating set again produces a dominating set with the same property of surviving forever. The eternal security number is the minimum size of an eternal dominating set. Notation that has been used for the eternal security number of G is γ∞(G).
Background: For example, the eternal security number of the 5-cycle C5 is 3, not 2. Given a dominating set S of size 2, the opponent could attack the vertex adjacent to both vertices of S, and after protecting it the defender would lose on the next move. In contrast, a mobile eternally secure set gives the defender more flexibility by allowing each army to move to a neighboring vertex on each move, and in this model two armies suffice to guard C5. These concepts were introduced (?) by Goddard, Hedetniemi, and Hedetniemi [GHH].
It is easy to observe that α(G)≤γ∞(G)≤θ(G), where α(G) is the independence number and θ(G) is the clique cover number (minimum number of complete subgraphs needed to cover the vertices). Also, Klostermeyer and MacGillivray [KM2] proved that γ∞(G)≤a(a+1)/2, where a=α(G). This result is nontrivial; it improves the same upper bound having been proved for the mobile eternal security number ([GHH?]). Goldwasser and Klostermeyer showed that equality holds for infinitely many graphs.
Question 1: Characterize the graphs that achieve equality in these bounds. In particular, is it true that γ∞(G)=θ(G) whenever G is a planar graph?
Partial results: All graphs not having K4 as a minor satisfy γ∞(G)=θ(G) ([ABBCVY]). This also holds for all circular-arc graphs ([R]). The smallest known graph satisfying γ∞(G)<θ(G) has 11 vertices. The smallest known graph with independence number 3 that satisfies γ∞(G)=3(3+1)/2 has 22 vertices.
Note that independence number and clique-cover number are dual integer programs. Another parameter trapped between them is the Lovász theta function, which equals √5 for C5. This suggests:
Question 2: Is γ∞ bounded below by the Lovász theta function?
[GHH] conjectured that if γ∞(G)=α(G), then α(G)=&theta(G). [KM1] proved that this is true when α(G)=2, but they provided counterexamples when α(G)=3. They posed some additional questions. Complexity of various questions concerning eternal dominating sets is studied in [K].
References:
[ABBCVY] M. Anderson, C. Barrientos, R. Brigham, J. Carrington,
R. Vitray, and J. Yellen; Maximum demand graphs for eternal security,
J. Combin. Math. Combin. Comput.} 61 (2007), 111--128.
[GHH] Goddard, Wayne; Hedetniemi, Sandra M.; Hedetniemi, Stephen T.; Eternal
security in graphs. J. Combin. Math. Combin. Comput. 52 (2005), 169--180.
[K] Klostermeyer, W.F.; Complexity of eternal security.
J. Combin. Math. Combin. Comput. 61 (2007), 135--140.
[KM1] Klostermeyer, W.F.; MacGillivray, G.; Eternally secure sets, independence
sets and cliques. AKCE Int. J. Graphs Comb. 2 (2005), no. 2, 119--122.
[KM2] Klostermeyer, W.F.; MacGillivray, G.; Eternal security in graphs of fixed
independence number. J. Combin. Math. Combin. Comput. 63 (2007), 97--101.
[R] F. Regan, Dynamic variants of domination and independence in graphs,
graduate thesis, Rheinischen Friedrich-Wilhlems University, Bonn, 2007.