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 vertics 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 ro move in response to an attack and (iii) whether at most one or more than one guard is allowed on a vertex at a time.

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 incorrect
  • 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, to appear in Math Slovaca (2012).
  • 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, to appear in Discrete Applied Mathematics, (2012)
  • J. Goldwasser, W. Klostermeyer, and C. Mynhardt, Eternal Protection in Grids, to appear in Utilitas Mathematica (2013)
  • 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, to appear in JCMMCC
  • W. Klostermeyer, M. Lawrence, and G. MacGillivray, An Eternal Domination Problem Related to File Migration
  • W. Klostermeyer and C.M. Mynhardt, Dynamic Domination in Trees
  • F. Regan, Dynamic variants of domination and independence in graphs, graduate thesis, Rheinischen Friedrich-Wilhlems University, Bonn, 2007.