The eternal domination number 
is the smallest cardinality
of an eternal dominating set of a graph 
in the one-guard model. It is the least number of guards that can defend every sequence
of attacks on unoccupied vertices. Initially the
occupied vertices form a dominating
set. At each attack, exactly one guard moves along an graph
edge to the attacked graph vertex, and the occupied
vertices must again form a dominating
set.
If 
is the domination number and 
is the clique
covering number, then
 |
The upper bound follows by keeping one guard in each clique of a clique partition. The gamma-theta
conjecture asserted that 
implies 
. Adamczewski and Klostermeyer (2026) disproved
it using the graph complement of the Berlekamp-van
Lint-Seidel graph, which has domination number
and eternal domination number both equal to 3 but clique
covering number greater than 3.
