Eternal k-domination on graphs

Eternal domination is a dynamic process by which a graph is protected from an infinite sequence of vertex intrusions. In eternal $k$-domination, guards initially occupy the vertices of a $k$-dominating set. After a vertex is attacked, guards "defend" by each move up to distance $k$ to form a $k$-dominating set containing the attacked vertex. The eternal $k$-domination number of a graph is the minimum number of guards needed to defend against any sequence of attacks. The process is well-studied for the $k=1$ situation and we introduce eternal $k$-domination for $k > 1$. Determining if a given set is an eternal $k$-domination set is in EXP, and in this paper we provide a number of results for paths and cycles, and relate this parameter to graph powers and domination in general. For trees we utilize decomposition arguments to bound the eternal $k$-domination numbers, and solve the problem entirely in the case of perfect $m$-ary trees.