Edge protection in graphs.
William F. Klostermeyer, Christina M. Mynhardt · Australas. J Comb. · 2009
We use mobile guards on the vertices of a graph to defend it against an infinite sequence of attacks on its edges. A guard on an incident vertex moves across the attacked edge to defend it; other guards may also move to neighboring vertices. We prove upper and lower bounds on the minimum number of guards needed for this eternal vertex cover problem and characterize the graphs for which the upper bound is sharp.