Eternal Domination is concerned with protecting a graph against an
infinite sequence of attacks by use of mobile guards located at some of
the vertices of the graph. There are several different models and
varieties of problems depending on (i) whether attacks are at vertices or
edges (if attacks are at edges, the problem is known as the Eternal Vertex
Cover Problem) (ii) whether only one or all guards all allowed to move in
response to an attack (iii) whether at most one or more than one guard is
allowed on a vertex at a time (iv) whether a guard must visit an attacked
vertex (the usual model) or leave an attacked vertex (the eviction model).
The following is a partial bibilography on the subject:
M.Anderson, C.Barrientos, R.Brigham, J.Carrington,
R.Vitray, and J.Yellen, Maximum demand graphs for eternal
security, J. Combin. Math.Combin.Comput. vol. 61 (2007), 111-128.
A.P.Burger, E.J.Cockayne, W.R.Grundlingh, C.M.Mynhardt,
J.H.van Vuuren and W.Winterbach, Infinite order domination in
graphs, J. Combin.Math.Combin.Comput., vol. 50 (2004), 179-194.
E. Chambers, W. Kinnersly, and N. Prince, Mobile eternal security in graphs, manuscript (2008).
F.Fomin, S.Gaspers, P.Golovach, D.Kratsch, S.Saurabh, Parameterized algorithm for eternal vertex cover,
Information Processing Letters, vol. 110 (2010), pp. 702-706.
W.Goddard, S.M.Hedetniemi and S.T.Hedetniemi, Eternal
security in graphs, J. Combin.Math.Combin.Comput., vol. 52 (2005), 169--180.
J.Goldwasser and W.F.Klostermeyer, Tight bounds for eternal
dominating sets in graphs, Discrete Math. vol. 308 (2008), 2589-2593.
W.F. Klostermeyer, Complexity of Eternal Security,
J. Comb. Math. Comb. Comput., vol. 61 (2007), pp. 135-141 (**) See Claim that eternal domination is in co-NP^NP is
W.F.Klostermeyer and G.MacGillivray, Eternal security in graphs
of fixed independence number, J. Combin.Math.Combin.Comput., vol. 63 (2007), 97-101.
W. F. Klostermeyer and G. MacGillivray, Eternally Secure Sets, Independence Sets, and Cliques,
AKCE International Journal of Graphs and Combinatorics, vol. 2 (2005), pp.119-122.
W.F.Klostermeyer and G.MacGillivray, Eternal dominating sets
in graphs, J. Combin.Math.Combin.Comput., vol. 68 (2009), pp.97-111.
W.F.Klostermeyer and G.MacGillivray, Foolproof Eternal Domination in the All-guards Move
Model, Math Slovaca (2012) pp.595-610
W.F.Klostermeyer and C.M.Mynhardt, Eternal total domination in graphs,
Ars Comb. 68 (2012), pp. 473-492
W.F.Klostermeyer and C.M.Mynhardt, Edge Protection in Graphs,
Australas.J.Combin. vol. 45(2009), 235-250.
W.F.Klostermeyer and C.M.Mynhardt, Graphs with Equal Eternal Vertex Cover and
Eternal Domination Numbers, Discrete Mathematics, vol. 311 (2011), pp.
1371-1379 (**) See Correction to Proposition 18
W.F.Klostermeyer, and C.M.Mynhardt, Vertex Covers and Eternal
Dominating Sets, Discrete Applied Mathematics 160 (2012), pp. 1183-1190
J. Goldwasser, W. Klostermeyer, and C. Mynhardt, Eternal Protection in
Grids, Utilitas Mathematica (2013), 47-64
W. Klostermeyer, Some Questions on Graph Protection, W. Klostermeyer,
Graph Theory Notes, vol 57 (2010), pp. 29-33
W. Klostermeyer and G. MacGillivray, Eternal Domination in Trees, to
appear in JCMCC
W.Klostermeyer and C.M. Mynhardt, Protecting a Graph with Mobile
Guards (survey), to appear
W. Klostermeyer, An Eternal Vertex Cover Problem, JCMMCC 85 (2013),
W. Klostermeyer, M. Lawrence, and G. MacGillivray, An Eternal
Domination Problem Related to File Migration, to appear in JCMCC
W. Klostermeyer and C.M. Mynhardt, Dynamic Domination in Trees
W. Klostermeyer and C.M. Mynhardt, Domination, Eternal Domination,
and Clique Covering, to appear in DMGT
F. Regan, Dynamic variants of domination and independence in graphs, graduate thesis, Rheinischen Friedrich-Wilhlems University, Bonn, 2007.
I. Beaton, S. Finbow and J. MacDonald, Eternal domination number of 4
by N grid graphs, JCMCC 85 (2013)