Bounds for the $m$-Eternal Domination Number of a Graph


  • Michael Henning University of Johanneburg
  • William Klostermeyer University of North Florida
  • Gary MacGillivray University of Victoria



dominating set, eternal dominating set, independent set, cubic graph, bipartite graph


Mobile guards on the vertices of a graph are used to defend the graph against an infinite sequence of attacks on vertices. A guard must move from a neighboring vertex to an attacked vertex (we assume attacks happen only at vertices containing no guard and that each vertex contains at most one guard). More than one guard is allowed to move in response to an attack. The $m$-eternaldomination number, $\edom(G)$, of a graph $G$ is the minimum number of guards needed to defend $G$ against any such sequence. We show that if $G$ is a connected graph with minimum degree at least~$2$ and of order~$n \ge 5$, then $\edom(G) \le \left\lfloor \frac{n-1}{2} \right\rfloor$, and this bound is tight. We also prove that if $G$ is a cubic bipartite graph of order~$n$, then $\edom(G) \le \frac{7n}{16}$.

Author Biographies

Michael Henning, University of Johanneburg

Department of Pure and Applied Mathematics

William Klostermeyer, University of North Florida

School of Computing

Gary MacGillivray, University of Victoria

Department of Mathematics and Statistics


A.P. Burger, E.J. Cockayne, W.R. Grundlingh, C.M. Mynhardt, J.H. van Vuuren, W. Winterbach, Infinite order domination in graphs. J.Combin. Math. Combin. Comput. 50 (2004), 179--194.

E. Chambers, W. Kinnersly, N. Prince, Mobile eternal security in graphs, manuscript (2008).

S. Finbow, M.-E. Messinger, M. van Bommel, Eternal domination in $3 \times n$ grids. Australas. J. Combin. 61 (2015), 156-174.

W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput. 52 (2005), 169-180.

J. Goldwasser, W. Klostermeyer, C. M. Mynhardt, Eternal protection in grid graphs. Utilitas Math. ~\textbf{91} (2013), 47--64.

T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs. Marcel Dekker, New York, 1998.

M. A. Henning, I. Schiermeyer, A. Yeo, A new bound on the domination number of graphs with minimum degree two, Electronic Journal of Combinatorics 18 (2011), paper P12.

W. Klostermeyer, G. MacGillivray, Eternally secure sets, independence sets, and Cliques. AKCE Int. J. Graphs Comb. 2 (2005), 119-122.

W. Klostermeyer, G. MacGillivray, Eternal dominating sets in graphs, J. Combin. Math. Combin. Comput. 68 (2009), 97-111.

W. Klostermeyer, G. MacGillivray, Eternal domination in trees, to appear in J. Combin. Math. Combin. Comput. (2015).

W. Klostermeyer, C.M.~Mynhardt, Vertex covers and eternal dominating sets, Discrete Applied Mathematics 160 (2012), pp. 1183-1190.

W. Klostermeyer, C.~M.~Mynhardt, Protecting a graph with mobile guards,

A. Kostochka, B. Stodolsky, On domination in connected cubic graphs, Discrete Math. 304 (2005), pp. 45--50.

A. V. Kostochka, C. Stocker, A new bound on the domination number of connected cubic graphs. Sib. Elektron. Mat. Izv. 6 (2009), 465–504.

W. McCuaig, B. Shepherd, Domination in graphs with minimum degree two. J. Graph Theory 13 (1989), 749-762.

O. Ore, Theory of graphs. Amer. Math. Soc. Transl. 38 (Amer. Math. Soc., Providence, RI, 1962), 206--212.

J. Petersen, Die theorie der regulären graphs, Acta Mathematica 15 (1891), pp. 193-220.

B. Reed, Paths, stars, and the number three, Combin. Probab. Comput. 5 (1996), pp. 277--295.