Menu
Results are presented on the eternal domination problem: defending a graph from an infinite sequence of attacks, so that each attack is defended by a guard at most distance one from the attack. We first consider the model where at most one guard moves to defend an attack. Our focus is on the relationship between the number of guards and the independence and clique covering numbers of the graph. We establish results concerning which triples of these parameters can be attained by some graph, and determine the exact value of the number of guards for graphs in certain classes. We then turn our attention to the variant of the problem in which every guard can relocate to an adjacent vertex in defence of an attack. We give a linear algorithm to determine the minimum number of guards necessary to defend a tree, and use it to answer another question about defending trees.