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)$.