2021/04/08 by Danielle Cox, Erin Meger, Cox, Danielle +3
Computer Science · Decision Sciences · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.2104.03835
openalex publication_date 2021/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Eternal domination is a dynamic process by which a graph is protected from an infinite sequence of vertex intrusions. In eternal distance-k domination, guards initially occupy the vertices of a distance-k dominating set. After a vertex is attacked, guards ``defend'' by each moving up to distance k to form a distance-k dominating set, such that some guard occupies the attacked vertex. The eternal distance-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 situation where k=1. We introduce eternal distance-k domination for k > 1. Determining whether a given set is an eternal distance-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 use decomposition arguments to bound the eternal distance-k domination numbers, and solve the problem entirely in the case of perfect m-ary trees.