An eternal dominating set of a simple graph 
is a dominating
set on which guards can be placed, one at each occupied graph
vertex, so that every sequence of attacks can be successfully defended in the
one-guard model. Each attack occurs at an unoccupied graph
vertex. Exactly one guard moves along an graph edge
to the attacked graph vertex, and the occupied vertices must again form a dominating
set. The guards remain in their new positions for the next attack (Klostermeyer
and Mynhardt 2016).
The requirement is that a defense strategy works indefinitely, with each response chosen using only attacks that have already occurred. Equivalently, an eternal dominating set belongs to a family of dominating sets of the same size such that every attack on every member has a legal response leading to another member of the family.
A minimum eternal dominating set has the smallest possible cardinality, which is the eternal domination number 
. An eternal dominating
set need not be minimum.
For example, the middle graph vertex of the three-vertex path graph 
is a dominating set by
itself, but it is not an eternal dominating set. An attack on either end forces its
sole guard to move there, leaving the other end unprotected. Every pair of vertices
is an eternal dominating set, since any attack can be answered by moving a guard
to the sole unoccupied graph vertex, leaving another
pair. Thus the three pairs are minimum eternal dominating sets, while the full vertex set is a larger eternal dominating set.
