Problems / combinatorics
combinatorics / Graph theory
The γ–θ conjecture in eternal domination
Let H be the Berlekamp–van Lint–Seidel graph on 243 vertices, the Cayley graph of Z35 with strongly regular parameters
(243,22,1,2),
and let G=H.
The proof establishes
γ(G)=3
because every pair has a common neighbor in H, while an H-triangle gives a dominating triple in G.
It then proves
γ∞(G)=3
by showing that the family of all dominating triples is closed under a legal response to every attack: after moving one guard to the attacked vertex, another dominating triple can always be obtained.
Finally, a double-counting argument shows that H is not 3-colorable, hence
θ(G)=χ(H)>3.
Therefore
γ(G)=γ∞(G)=3<θ(G).