Abstract
Assuming the published exclusion through order 11, no graph on 12 vertices is a counterexample to the one-guard \(\gamma\)–\(\theta\) conjecture.
MacGillivray, Mynhardt, and Virgile reported an exhaustive computation excluding counterexamples through order 11. This paper extends that published frontier by closing every possible common parameter at order 12: \(k=3\) and \(k=4\) by independently replayed proof certificates, and \(k=5\) by a structural reduction and a classical domination bound.
*Explicitly conditional on the published exhaustive result through order 11.
Main theorem
Theorem. Assume the published exhaustive result of MacGillivray, Mynhardt, and Virgile that no counterexample has order at most \(11\). Then no finite simple graph \(G\) of order at most \(12\) satisfies
Equivalently, every counterexample, if one exists, has order at least \(13\).
Here \(\theta(G)=\chi(\overline G)\) is the clique-cover number. The paper concerns the standard one-guard-moves eternal domination game, with attacks only at unoccupied vertices. It does not concern the all-guards-move model or the Lovász theta function \(\vartheta\).
Proof and certificate architecture
| Slice | Evidence |
|---|---|
| \(k=3\) | A complete induced-odd-hole template split; exact graph-to-CNF theorems; three checked addition-only RUP proofs; two independent composition reviews |
| \(k=4\) | An exact 18,381-variable, 115,507-clause formula; sound DoubleLex orbit reduction; a 228,381,671-byte LRAT refutation; independent formula and implication audits |
| \(k=5\) | A proved simplicial closed-neighborhood reduction; minimum-counterexample connectedness; the McCuaig–Shepherd minimum-degree-two domination bound |
| Coverage | The parameter chain and the classical half-order characterization show that \(3,4,5\) are the only possible order-12 values |
The full replay checks exact bytes and theorem bindings before running the proof checkers. No SAT solver is needed to verify the retained certificates.
Structural byproducts
The paper proves a simplicial closed-neighborhood theorem for equality graphs and an unrestricted, family-level independent-antineighborhood projection. If \(\gamma(G)=\gamma^\infty(G)=k\) and \(A\) is an independent \(t\)-set with \(t<k\), then \(G-N[A]\) has all three parameters \(\gamma,\alpha,\gamma^\infty\) equal to \(k-t\), and every eternal family projects explicitly. For a minimum counterexample, its clique-cover number also equals \(k-t\).
The paper carefully records direct overlap with Taletskii's planar minimum-counterexample lemma and does not present the older antineighborhood idea as wholly new.
Attribution, scope, and limitations
The through-order-11 computation is due to Gary MacGillivray, C. M. Mynhardt, and V. Virgile. The present candidate contribution is the order-12 extension and its exact proof package. The campaign independently reproduced their appendix parameters but did not repeat their cluster-scale all-graph enumeration at orders 10 and 11.
No claim is made at order 13 or above in this paper. No universal proof or counterexample has been obtained, no external expert was contacted, and no external review has occurred.
AI-assistance and verification disclosure
The exploratory mathematics, programs, certificate design, adversarial audits, literature review, manuscript, and publication materials were developed with substantial assistance from ChatGPT 5.6 Sol under Alec Kriebel's direction. No theorem or finite claim was accepted on model output alone. Passing the supplied checks is not peer review.
Suggested citation
Alec Kriebel, “A Certified Order-Twelve Extension of the \(\gamma\)–\(\theta\) Frontier in One-Guard Eternal Domination,” provisional research paper, 26 July 2026. Permanent paper page.