Closing the Gap: Eternal Domination on 3 x n Grids


  • Margaret-Ellen Messinger Mount Allison University



graph protection, all guards move, m-eternal domination


The domination number for grid graphs has been a long studied problem; the first results appeared over thirty years ago [Jacobson 1984] and the final results appeared in 2013 [Goncalves 2013]. Grid graphs are a natural class of graphs to consider for the eternal dominating set problem as the domination number forms a lower bound for the eternal domination number.  The 3 x n grid has been considered in several papers, and the difference between the upper and lower bounds for the eternal domination number in the all-guards move model has been reduced to a linear function of n. In this short paper, we provide an upper bound for the eternal domination number which exceeds the lower bound by at most 3.



[1] J. Arquilla, H. Fredricksen, “Graphing” an Optimal Grand Strategy, Military Operations Research 1(3) (1995) 3-17.

[2] I. Beaton, S. Finbow, J.A. MacDonald, Eternal Domination Numbers of 4 × n Grid Graphs, J. Combin. Math. Combin. Comput. 85 (2013) 33-48.

[3] S. Finbow, S. Gaspers, M.E. Messinger, P. Ottaway, A note on the eternal dominating set problem, submitted.

[4] S. Finbow, M.E. Messinger, M. van Bommel, Eternal Domination of 3 × n grid graphs, Aust. J. of Combin. 61(2) (2015) 156–174.

[5] W. Goddard, S.M Hedetniemi, S.T. Hedetniemi, Eternal Security in Graphs, J. Combin. Math. Combin. Comput. 52 (2005) 169–180.

[6] J.L. Goldwasser, W.F. Klostermeyer, C.M. Mynhardt, Eternal Protection in Grid Graphs, Util. Math. 91 (2013) 47–64.

[7] D. Gonc ̧alves, A. Pinlou, M. Rao, S. Thomass ́e, The Domination Number of Grids, SIAM J. Discrete Math. 25(3), (2011) 1443–1453.

[8] M.S. Jacobson, L.F. Kinch, On the Domination Number of Products of Graphs: I, Ars Combin. 18 (1984) 33–44.

[9] W.F. Klostermeyer, G. MacGillivray, Eternal Dominating Sets in Graphs, J. Combin. Math. Combin. Comput. 68 (2009) 97–111.

[10] W.F. Klostermeyer, C.M. Mynhardt, Protecting a Graph with Mobile Guards (submitted).

[11] C.S. ReVelle, Can You Protect The Roman Empire? John Hopkins Magazine, 50(2), April 1997.

[12] C.S. ReVelle, K.E. Rosing, Defendens Imperium Romanum: A Classical Problem in Military Strategy,

The American Mathematical Monthly 107(7), August - September 2000, 585–594.

[13] I. Stewart, Defend the Roman Empire! Scientific American, December 1999, 136-138.