Pith. sign in

REVIEW 6 minor 13 references

Connected Cayley graphs can force eternal domination at least two above ordinary domination.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-11 22:13 UTC pith:5V6MZFEB

load-bearing objection Solid combinatorial paper that answers Braga et al.’s open question with the first infinite connected Cayley family of gap at least 2, plus a clean equality theorem for vertex-transitive graphs with efficient dominating sets.

arxiv 2607.04024 v1 pith:5V6MZFEB submitted 2026-07-04 math.CO

Eternal domination in Cayley graphs

MacKenzie Carr , Nancy E. Clarke , Gary MacGillivray , Joy Morris This is my paper
classification math.CO MSC 05C2505C69
keywords eternal dominationCayley graphsefficient dominating setvertex-transitive graphsgeneralised dihedral groupsdomination numbermobile guards
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Eternal domination asks how many mobile guards must sit on a graph so that after any infinite sequence of attacks they can always reconfigure into a new dominating set, with one guard forced to the attacked vertex. For ordinary graphs the gap between this number and the usual domination number can be large; for highly symmetric Cayley graphs it was long thought to be zero, until isolated examples of gap one appeared. This paper proves that every vertex-transitive graph that admits an efficient dominating set (a perfect packing of closed neighbourhoods) has gap zero, and then constructs two infinite families of connected Cayley graphs: one with gap exactly one and one with gap at least two. The constructions answer, in the affirmative, the open question whether a connected Cayley graph can force a gap larger than one, and supply the first systematic infinite supply of such examples.

Core claim

There exist infinite families of connected Cayley graphs on which the eternal domination number exceeds the ordinary domination number by one, and by at least two. In particular, for every odd integer k ≥ 17 the Cayley graph Δ_k satisfies γ_all^∞(Δ_k) ≥ γ(Δ_k)+2, while for every odd k ≥ 5 the simpler Cayley graph Γ_k satisfies equality with gap exactly one. Separately, any vertex-transitive graph that possesses an efficient dominating set has eternal domination number equal to its domination number.

What carries the argument

Structural classification of all minimal (and near-minimal) dominating sets via left cosets of carefully chosen cyclic subgroups K'_k and B_k, together with an overlap counting argument that forces every small dominating set in Δ_k to contain an entire left coset of ⟨K'_k,b⟩; the same coset geometry then blocks reconfiguration across the two cosets of ⟨H_k,b⟩.

Load-bearing premise

The counting inequalities that force every dominating set of size at most 2k+1 in Δ_k to contain a full left coset of a certain cyclic subgroup become valid only once k is at least 17; if those inequalities fail for some larger odd k the gap-of-two claim collapses.

What would settle it

Explicitly compute, for some odd k ≥ 17, a dominating set of size 2k+1 in Δ_k that does not contain any left coset of ⟨K'_k,b⟩, or exhibit a legal reconfiguration of guards from one such coset to a dominating set that meets the opposite coset of ⟨H_k,b⟩.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper studies the eternal domination number γ_all^∞ in the all-guards-move model for Cayley graphs. It proves that any vertex-transitive graph possessing an efficient dominating set satisfies γ_all^∞=γ (Corollary 2.2). It then shows that many Cayley graphs on generalised dihedral groups (connection sets meeting the nontrivial coset of the abelian subgroup in at most two elements, or in all but at most one) have γ_all^∞=γ. The main constructions are two infinite families of connected Cayley graphs: Γ_k (odd k≥3) on groups of order 2k^{2} with γ_all^∞=γ+1, generalising the single example of Braga et al., and Δ_k (odd k≥17) on groups of order 4k^{2} with γ_all^∞≥γ+2, giving the first connected Cayley examples with gap larger than 1.

Significance. The work answers the open question of Braga et al. by exhibiting an infinite family of connected Cayley graphs with γ_all^∞≥γ+2, and simultaneously supplies the first infinite family with exact gap 1. The equality result for vertex-transitive graphs that admit efficient dominating sets is short, clean, and immediately applicable to many Cayley graphs (including those treated in Section 3). All arguments are direct combinatorial constructions and counting; there are no fitted parameters or circular reductions. The contribution is therefore a genuine advance on the structural theory of eternal domination for highly symmetric graphs.

minor comments (6)
  1. Throughout Sections 4 and 5 the text systematically refers to earlier lemmas as “Theorem” (e.g., “Using Theorem 4.4”, “by Theorem 5.3”, “Theorem 5.12”). These should be corrected to “Lemma” (or the statements renumbered) for consistency with the displayed environments.
  2. Section 4, Theorem 4.8 (k=3 case): the claim γ(Γ_3)≤k+1 is attributed to a computer check in Braga et al. without a short self-contained verification or explicit citation of the relevant computation. A one-paragraph hand check or a pointer to a reproducible enumeration would make the base case fully independent of external software.
  3. Section 5 opens with a long chain of overlap and coset lemmas (5.3–5.12) before the reconfiguration obstruction appears. A short roadmap paragraph at the beginning of the section, listing the successive structural constraints that force every dominating set of size ≤2k+1 to contain a left coset of ⟨K'_k,b⟩, would greatly improve readability.
  4. Figures 1–3 are helpful but the captions do not explicitly mark the two cosets of H_k (or of ⟨H_k,b⟩) or the left cosets of K_k / B_k. Adding a one-sentence legend would make the diagrams self-contained.
  5. The authors note that they stop at the lower bound γ_all^∞≥γ+2 for Δ_k. While this is sufficient for the open problem, a brief remark on whether an upper bound of γ+2 (or even γ+O(1)) is expected would help the reader gauge the tightness of the construction.
  6. Minor typographical points: “It it true” (p. 2), “generalised”/“generalized” inconsistency, and occasional missing spaces around mathematical operators. A careful proof-reading pass will catch these.

Circularity Check

0 steps flagged

No significant circularity: all main claims are proved by direct combinatorial constructions and counting arguments on explicitly defined Cayley graphs.

full rationale

The paper’s derivation chain is self-contained finite-group combinatorics. Corollary 2.2 follows from a matching argument on efficient dominating sets (Proposition 2.1) that does not presuppose the eternal-domination conclusion. The equality results for generalized dihedral Cayley graphs (Theorems 3.2, 3.6, Corollary 3.5) are proved by explicit reconfiguration maps and coset partitions; the citation of Morris–Smolčić [11] supplies only an isomorphism criterion that is not required for the later gap results. The infinite families Γ_k (γ_all^∞ = γ+1) and Δ_k (γ_all^∞ ≥ γ+2) are defined by concrete generators and connection sets; lower bounds come from degree counting, structural classification of minimal dominating sets proceeds by overlap and coset-counting lemmas (valid for k≥5 and k≥17 respectively), and the reconfiguration obstructions (Theorems 4.7, 5.15) are exhibited by direct case analysis. Braga et al. [1] is used only for the k=3 base case and as historical motivation, never as a load-bearing uniqueness or uniqueness-of-structure premise. There are no fitted parameters, no self-definitional loops, and no reduction of a claimed prediction to an earlier fitted constant. The derivation therefore does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 2 invented entities

The work is pure finite-group combinatorics. It relies only on standard definitions of Cayley graphs, domination, and eternal domination, plus elementary facts about generalized dihedral groups and cosets. No free parameters are fitted; the only 'invented' objects are the concrete families of groups and connection sets constructed for the gap examples.

axioms (4)
  • standard math Standard definition of the (all-guards-move) eternal domination number γ_all^∞ and the ordinary domination number γ.
    Used throughout; taken from Goddard et al. (2005) and subsequent literature.
  • standard math Cayley graphs are vertex-transitive; left multiplication by group elements yields automorphisms.
    Invoked repeatedly to reduce to the identity vertex and to transfer dominating sets.
  • standard math An efficient dominating set (perfect code) in a regular graph of order v and degree k exists only when k+1 divides v, and each vertex is dominated by exactly one codeword.
    Used in Section 2 to prove that the collection of all efficient dominating sets forms an eternal configuration.
  • domain assumption Definition of generalized dihedral group over an abelian group A and the partition of elements into those that centralize or invert a given reflection.
    Section 3; standard group-theoretic background needed for the reconfiguration argument of Theorem 3.2.
invented entities (2)
  • Family of groups G_k = ⟨ ho, au,a | ho^k= au^{2}=a^k=e, a central, au ho= ho^{-1} au⟩ ≅ D_{2k} imes C_k and the associated Cayley graphs Γ_k no independent evidence
    purpose: Provide an infinite family of connected Cayley graphs with γ_all^∞ = γ+1.
    Explicitly constructed in Definitions 4.1–4.2; no independent existence claim beyond the paper.
  • Extended groups ⟨G_k,b⟩ ≅ D_{2k} imes C_{2k} and Cayley graphs Δ_k with connection set T_k no independent evidence
    purpose: Provide an infinite family of connected Cayley graphs with γ_all^∞ ≥ γ+2.
    Definitions 5.1; again a pure construction internal to the paper.

pith-pipeline@v1.1.0-grok45 · 25333 in / 2857 out tokens · 19293 ms · 2026-07-11T22:13:23.398685+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Eternal domination in Cayley graphs." pith.science (2026). https://pith.science/paper/5V6MZFEB

@misc{pith2026260704024,
  author       = {Pith},
  title        = {Pith review of: Eternal domination in Cayley graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5V6MZFEB}},
  note         = {Machine review of arXiv:2607.04024}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Eternal domination is a process in which a set of guards occupying a dominating set on a graph protects against an infinite sequence of attacks. After a vertex is attacked, one guard must move along an edge to the attacked vertex and each of the remaining guards may move along an edge so that the guards again occupy a dominating set on the graph and can defend the next attack. The minimum number of guards needed in a graph $\Gamma$ is the eternal domination number, denoted by $\gamma_{\mathrm{all}}^\infty(\Gamma)$. In this paper, we show that the eternal domination number of a vertex-transitive graph with an efficient dominating set is equal to its domination number. We show that a Cayley graph on a generalized dihedral group whose connection set contains few or many reflections is efficiently dominated. Then, we provide an infinite family of connected Cayley graphs for which $\gamma_{\mathrm{all}}^{\infty}(\Gamma) = \gamma(\Gamma)+1$, generalizing a result of [Braga et al., J. Combin. Math. Combin. Comput. 96 (2016), 13--22]. Finally, we build an infinite family of connected Cayley graphs with $\gamma_{\mathrm{all}}^\infty(\Gamma) \geq \gamma(\Gamma)+2$.

Figures

Figures reproduced from arXiv: 2607.04024 by Gary MacGillivray, Joy Morris, MacKenzie Carr, Nancy E. Clarke.

Figure 1
Figure 1. Figure 1: The neighbours of e in Γ5 are indicated in black. Note that Hk and Ak are normal in Gk, while Kk and K′ k are not. However, Kk and K′ k are normal in Hk, so within that context we may occasionally refer to their “cosets”; within Gk we will be considering left cosets. Definition 4.2. Let k ≥ 3. We use Γk = Cay(Gk, Sk), where Sk = {τ ai , ρi a i : 1 ≤ i ≤ k − 1} ∪ {ρτ a, ρτ a−1 }. In everything that follows,… view at source ↗
Figure 2
Figure 2. Figure 2: The neighbours of τ in Γ5 are indicated in black. The vertex ρ j τ aℓ is dominated by ρ ja −j unless ℓ = −j. If ℓ = −j then this vertex is dominated by ρ j−1a 1−j using the element ρτ a−1 of the connection set. Thus every vertex that is not in Hk is also dominated by D. Thus, γ(Γk) = k. □ Next we have a lemma that tells us a lot about the structure of any minimal dominating set. Lemma 4.4. Let k ≥ 3 be odd… view at source ↗
Figure 3
Figure 3. Figure 3: The neighbours of e in ∆5 are indicated in black. Definition 5.1. For any odd k ≥ 3, we define the family of Cayley graphs ∆k as ∆k = Cay(⟨Gk, b⟩, Tk), where Tk = (Sk \ {ρa, ρ−1a −1}) ∪ {ρab, ρ−1a −1 b}. In [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references

  1. [1]

    Eternal security in graphs

    Andrei Braga, Cid de Souza, and Orlando Lee. A note on the paper “Eternal security in graphs” by Goddard, Hedetniemi, and Hedetniemi (2005).J. Combin. Math. Combin. Com- put.96(2016), 13–22

    2005

  2. [2]

    Tamizh Chelvam and Sivagnanam Mutharasu

    T. Tamizh Chelvam and Sivagnanam Mutharasu. Subgroups as efficient dominating sets in Cayley graphs,Discrete Appl. Math.161(9) (2013), 1187–1190

    2013

  3. [3]

    Efficient dominating sets in circulant graphs,Discrete Math.340(7) (2017), 1503–1507

    Yun-Ping Deng, Yu-Qin Sun, Qiong Liu and Hai-Chao Wang. Efficient dominating sets in circulant graphs,Discrete Math.340(7) (2017), 1503–1507

    2017

  4. [4]

    Efficient dominating sets in circulant graphs with domination number prime, Inf

    Yun-Ping Deng. Efficient dominating sets in circulant graphs with domination number prime, Inf. Process. Lett.114(12) (2014), 700–702

    2014

  5. [5]

    Perfect codes in circulant graphs,Discrete Math.340(7) (2017), 1522–1527

    Rongquan Feng, He Huang and Sanming Zhou. Perfect codes in circulant graphs,Discrete Math.340(7) (2017), 1522–1527

    2017

  6. [6]

    On perfect dominating sets in Cayley graphs,Discrete Appl

    Yan-Quan Feng, Rong-Xia Hao, Young Soo Kwon and Jaeun Lee. On perfect dominating sets in Cayley graphs,Discrete Appl. Math.376(2025), 160–166. 20 MACKENZIE CARR, NANCY E. CLARKE, GARY MACGILLIVRAY, AND JOY MORRIS

    2025

  7. [7]

    A note on the eternal dominating set problem.International journal of game theory,47(2018), 543–555

    Stephen Finbow, Serge Gaspers, Margaret-Ellen Messinger, and Paul Ottaway. A note on the eternal dominating set problem.International journal of game theory,47(2018), 543–555

    2018

  8. [8]

    Eternal security in graphs

    Wayne Goddard, Sandra Hedetniemi, and Stephen Hedetniemi. Eternal security in graphs. J. Combin. Math. Combin. Comput.52(2005), 169–180

    2005

  9. [9]

    Protecting a graph with mobile guards.Applic

    William Klostermeyer and Kieka Mynhardt. Protecting a graph with mobile guards.Applic. Anal. Discr. Math.10(2016), 1–29

    2016

  10. [10]

    Reji Kumar and Gary MacGillivray

    K. Reji Kumar and Gary MacGillivray. Efficient domination in circulant graphs,Discrete Math.313(6) (2013), 767–771

    2013

  11. [11]

    Two families of graphs that are Cayley on nonisomorphic groups,J

    Joy Morris and Josip Smolˇ ci´ c. Two families of graphs that are Cayley on nonisomorphic groups,J. Algebra Combinatorics Discrete Structures and Applications8(2021), 53–57

    2021

  12. [12]

    Ethan Williams

    J. Ethan Williams. Eternal domination problems. M.Sc. Thesis, University of Victoria, Victoria, BC, Canada (2023).https://dspace.library.uvic.ca/items/ 287c6f24-f776-4bce-a72c-df9f7a448134

    2023

  13. [13]

    Mobile guards’ strategies for graph protection and surveillance

    Virgelot Virgile. Mobile guards’ strategies for graph protection and surveillance. Ph.D. The- sis, University of Victoria, Victoria, BC, Canada (2024).https://dspace.library.uvic.ca/ items/4ff56e60-1878-4697-85ba-b34bf44ecea3 Department of Mathematics, Toronto Metropolitan University, Toronto, ON M5B 2K3, Canada Email address:mackenzie.carr@torontomu.ca D...

    2024