Abstract
The Lovász theta function can exceed the standard one-guard eternal domination number by an unbounded factor.
Combining Alon's explicit Ramsey graphs with a theorem of Goddard, Hedetniemi, and Hedetniemi gives an explicit family \((H_k)\) with \(2\leq\gamma^\infty(H_k)\leq3\) and \(\vartheta(H_k)=\Theta(|V(H_k)|^{1/3})\).
The smallest counterexample has ten vertices. For the graph with graph6 record IEhbtj{ro, an exact rational feasible matrix for the standard Lovász-theta semidefinite program has objective \(7593/2500=3.0372\), while the eternal domination number is exactly three.
An explicit unbounded separation
Theorem. For integers \(k\geq2\) with \(3\nmid k\), put \(n_k=2^{3k}\). There is an explicit graph \(H_k\) on \(n_k\) vertices satisfying
Consequently \(\vartheta(H_k)/\gamma^\infty(H_k)=\Theta(n_k^{1/3})\), so there is not even a constant-factor universal lower bound.
Alon's 1994 construction supplies explicit triangle-free Cayley graphs whose complements have theta value \(\Theta(n^{1/3})\). Goddard, Hedetniemi, and Hedetniemi proved that independence number two forces \(\gamma^\infty\leq3\). The theorem is their direct combination, not a new graph construction.
A smallest counterexample
Theorem. Let \(G\) have graph6 record IEhbtj{ro. Then
No graph on fewer than ten vertices satisfies \(\gamma^\infty(G)<\vartheta(G)\).
The graph itself and the equality \(\gamma^\infty(G)=3\) were published by MacGillivray, Mynhardt, and Virgile in 2022 in their work on a different parameter: clique-cover number. The finite contribution here is the exact Lovász-theta certificate and the minimum-order connection.
Exact evidence
| Claim | Check |
|---|---|
| Graph identity | Two independent graph6 decoders, a frozen 26-edge list, and a nauty cross-check |
| Theta feasibility | Trace one, all 26 edge entries zero, and ten positive exact rational \(LDL^{\mathsf T}\) pivots |
| Theta objective | Exact entry sum \(30372/10000=7593/2500\) |
| Eternal domination | Greatest fixed-point sizes \(0,0,86\) for one, two, and three guards |
| Three-guard defense | All 602 configuration-attack pairs checked in an 86-state closed family |
The verifier uses only exact integer and rational arithmetic in Python's standard library. No numerical SDP solver is part of the finite proof. It does not reconstruct Alon's asymptotic family, which is taken from the cited literature.
Minimum order
MacGillivray, Mynhardt, and Virgile computationally verified that every graph on at most nine vertices satisfies \(\gamma^\infty(G)=\operatorname{cc}(G)\). The theta sandwich inequality gives
Consequently no graph of order at most nine can violate the proposed inequality, and this ten-vertex graph has minimum possible order. This corollary relies on their published exhaustive computation; the local package does not re-enumerate every smaller graph.
Attribution, novelty, and scope
The ingredients of the unbounded-family theorem are established results. The point here is their immediate combination in connection with West's recorded question. The ten-vertex graph and its eternal-domination value are also prior work; the candidate finite contribution is the theta certificate and minimum-order identification.
A focused search found no prior public source explicitly making either connection as of 26 July 2026. The connections therefore appear unrecorded, but the search cannot establish absolute priority or exclude an unindexed or differently phrased antecedent.
No external expert was contacted or has reviewed the note.
AI-assistance and verification disclosure
The observation, exact certificates, independent verifiers, literature review, proof drafting, and publication materials were developed with heavy assistance from ChatGPT 5.6 Sol under Alec Kriebel's direction. Passing the supplied checks is not peer review.
Suggested citation
Alec Kriebel, with heavy assistance from ChatGPT 5.6 Sol, “Eternal domination and the Lovász theta function: an unbounded separation and a smallest counterexample,” revised provisional research note, first published 25 July 2026 and revised 26 July 2026. Permanent page.