MathDB

Gamma–Theta conjecture for eternal dominating sets

For every finite simple graph GG, if its ordinary domination number equals its eternal domination number, then it equals its upper domination number: γ(G)=γ∞(G) ⟹ γ(G)=θ(G)\gamma(G)=\gamma^{\infty}(G)\ \Longrightarrow\ \gamma(G)=\theta(G), equivalently, γ(G)=γ∞(G)\gamma(G)=\gamma^{\infty}(G) implies γ∞(G)=θ(G)\gamma^{\infty}(G)=\theta(G).

References

Primary source

arXiv

Additional references

domination-theorygraph-theory
Posted · edited

Progress summary

Refreshed
Claimed solved

A September 2026 preprint claims the conjecture is false by giving a 243-vertex counterexample, but the construction has not yet been independently checked.

The conjecture asserts that, for every graph GG, equality of ordinary and eternal domination numbers implies equality with the upper domination number: γ(G)=γ∞(G)⇒γ(G)=θ(G)\gamma(G)=\gamma^{\infty}(G)\Rightarrow\gamma(G)=\theta(G). It was explicitly stated in 2021; a 2026 preprint now claims to refute it.

Known results

  • Maximum degree at most 33: the implication holds (2014).
  • No counterexample was found by computer search for graphs of order n≤11n\le 11 (2021).
  • The implication was proved for planar graphs (2024).

September 10, 2026 counterexample claim

The preprint A Counterexample to an Eternal Domination Conjecture, by Tom Adamczewski and William F. Klosterman, reports an explicit 243243-vertex graph refuting the universal implication. If its computational or structural certificate is correct, the conjecture is false.

Current status (as of September 2026): A 243243-vertex counterexample is claimed, while verification of the refutation remains open; the bounded-degree, small-order search, and planar cases remain established.

Sources

Solutions 0

No solutions have been posted yet.