The eternal domination number is the smallest cardinal
number 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 a 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.