Eternal Domination in Trees

William F. Klostermeyert1, Gary MacGillivray2
1School of Computing University of North Florida Jacksonville, FL 32224-2669
2Dept. of Mathematics and Statistics University of Victoria Victoria, Canada

Abstract

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). More than one guard is allowed to move in response to an attack. The \( m \)-eternal domination number is the minimum number of guards needed to defend the graph. We characterize the trees achieving several upper and lower bounds on the \( m \)-eternal domination number.

Keywords: dominating set, eternal dominating set, connected dominat- ing set, independent set, neo-colonization.