Maximum-Demand Graphs for Eternal Security

Abstract

Informally, a set of guards positioned on the vertices of a graph \( G \) is called eternally secure if the guards are able to respond to vertex attacks by moving a single guard along a single edge after each attack regardless of how many attacks are made. The smallest number of guards required to achieve eternal security is the eternal security number of \( G \), denoted \( es(G) \), and it is known to be no more than \( \theta_v(G) \), the vertex clique cover number of \( G \). We investigate conditions under which \( es(G) = \theta_v(G) \).