TOPICS
Search

Gamma-Theta Conjecture

The gamma-theta conjecture is a refuted conjecture asserting that a graph G whose domination number gamma(G) equals its one-guard eternal domination number gamma^infty(G) must also satisfy gamma(G)=theta(G), where theta(G) is its clique covering number (Adamczewski and Klostermeyer 2026).

Adamczewski and Klostermeyer (2026) disproved the conjecture using the graph complement G of the 243-vertex Berlekamp-van Lint-Seidel graph, for which

gamma(G)=gamma^infty(G)=3<theta(G).

Their computation verifies that every attack on an unoccupied graph vertex can be defended by moving one guard from any of the 1987821 three-vertex dominating sets to obtain another three-vertex dominating set. This closure property gives a strategy for an arbitrarily long sequence of attacks, so all these triples are eternal dominating sets.

The construction originated in an experiment by Adamczewski (2026) in which GPT-6 Astra identified the graph and produced a defense strategy and Lean proof (VibeMathed 2026). Adamczewski and Klostermeyer (2026) subsequently supplied a mathematical account and computational verification.

See also

Berlekamp-van Lint-Seidel Graph, Clique Covering Number, Domination Number, Eternal Dominating Set, Eternal Domination Number

Explore with Wolfram|Alpha

References

Adamczewski, T. "The Gamma-Theta Conjecture in Eternal Domination." 2026. https://github.com/tadamcz/gamma-theta.Adamczewski, T. and Klostermeyer, W. F. "A Counterexample to an Eternal Domination Conjecture." 10 Sep 2026. https://arxiv.org/abs/2609.11500.VibeMathed. "The Gamma-Theta Conjecture in Eternal Domination." 2026. https://vibemathed.com/problem/counterexample-to-the-gamma-theta-conjecture-in-eternal-domination.

Cite this as:

Weisstein, Eric W. "Gamma-Theta Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Gamma-ThetaConjecture.html

Subject classifications