AI Proof WatchKeep up with AI contributions

The gamma–theta eternal-domination conjecture

If a graph’s domination number equals its one-guard-moves eternal domination number, must both equal its vertex clique-cover number? The eternal game requires guards to respond indefinitely to successive vertex attacks under the one-moving-guard rule.

Why it matters and what counts as progress

Why it matters: The equality proposal links static domination, an indefinite guard game and clique covers, which need not capture the same structure.

What counts as progress: Prove the equality for further classes or certify a graph with equal domination parameters strictly below clique-cover number.

How the problem developed

  1. 2021 · Conjecture and computation [1]

    Gary MacGillivray, C. M. Mynhardt, and Virgile Virgélot Stated the γ–θ conjecture and reported exhaustive computation finding no counterexample through 11 vertices.

  2. 2024 · Special case [2]

    Dmitry Taletskii Proved the conjecture for planar graphs, adding to known results for several restricted graph classes.

  3. 10 Sept 2026 · Counterexample [3]

    Tom Adamczewski and William F. Klostermeyer Constructed a 243-vertex graph with γ(G)=γ∞(G)=3<θ(G), disproving the universal conjecture in the one-guard-moves model.

AI contribution

Sources

  1. MacGillivray, Mynhardt, and Virgélot, Eternal Domination and Clique Covering
  2. Dmitry Taletskii, The Gamma-Theta Conjecture holds for planar graphs
  3. Adamczewski and Klostermeyer, A Counterexample to an Eternal Domination Conjecture
  4. AI counterexample account
  5. Original one-guard-moves challenge
  6. Lean proof of the γ–θ counterexample
  7. Klostermeyer’s human analysis
Website timeline

Publication dates and editorial changes.