Eternal Domination vs Domination Number

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $G=(V,E)$ be a finite simple undirected graph. A set $D\subseteq V$ dominates $G$ if every vertex lies in $D$ or is adjacent to a vertex of $D$; $\gamma(G)$ is the minimum size of a dominating set. In the one-guard-move eternal domination game, the defender initially occupies a dominating set with $k$ guards. At each turn the attacker chooses an unoccupied vertex $v$; exactly one guard moves along an edge to $v$, all other guards stay, and the new occupied set must dominate $G$. The least $k$ admitting a defense against every arbitrarily long sequence of attacks is $\gamma^\infty(G)$. Finally $\theta(G)$ is the minimum number of cliques partitioning $V$ (equivalently, covering $V$).

Statement recorded in the supplied source.

Does there exist a finite simple graph $G$ such that \[ \gamma(G)=\gamma^\infty(G)<\theta(G)? \] [S2]

Short English statement

Can the ordinary domination number equal the one-guard-move eternal domination number while both are strictly smaller than the clique covering number?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1389 (GRAPH-002). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Tom Adamczewski and William F. Klostermeyer, A Counterexample to an Eternal Domination Conjecture (2026), arXiv:2609.11500v1, Sections 1--3, especially Conjecture 3.1. https://arxiv.org/abs/2609.11500v1.