Eternal k-domination on graphs
share
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.
READ FULL TEXT