pith. sign in

arxiv: 2507.11871 · v2 · pith:CXQM324Inew · submitted 2025-07-16 · 🧮 math.CO

Perfect codes in Cayley graphs of abelian groups

Peter J. Cameron , Roro Sihui Yap , Sanming Zhou This is my paper

Pith reviewed 2026-05-22 00:22 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C2505C69
keywords perfect codestotal perfect codesCayley graphsfinite abelian groupsdominating setsgraph theory
0
0 comments X

The pith

Cayley graphs of finite abelian groups contain perfect codes and total perfect codes for suitable connection sets.

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

The paper defines a perfect code as an independent set where every non-code vertex has exactly one neighbor in the set, and a total perfect code as a set where every vertex has exactly one neighbor in the set. It then proves several results about the existence and structure of both kinds of codes inside Cayley graphs built from finite abelian groups. These graphs are vertex-transitive, so the group operation lets the authors translate code properties into statements about subsets of the group itself. A reader would care because such codes give explicit algebraic constructions for dominating sets and error-correcting configurations in highly symmetric networks.

Core claim

In this paper we prove several results on perfect codes and total perfect codes in Cayley graphs of finite abelian groups.

What carries the argument

The Cayley graph of a finite abelian group, whose vertices are group elements and whose edges are determined by a connection set; the group action turns code conditions into arithmetic statements on the group.

If this is right

  • The group order and the size of the connection set must satisfy a simple numerical relation for such a code to exist.
  • Explicit constructions of the codes can be obtained by taking cosets or subgroups of the abelian group.
  • The same graphs may admit both perfect codes and total perfect codes under different choices of connection set.
  • Results supply new families of graphs in which the domination number equals the size of a perfect code.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same techniques could be tested on non-abelian groups to see whether commutativity is essential.
  • Computational enumeration on small groups such as Z_6 or Z_2 x Z_3 would produce explicit examples that illustrate the proved statements.

Load-bearing premise

The definitions of perfect code and total perfect code apply directly to the vertex-transitive structure of Cayley graphs on finite abelian groups without additional regularity conditions on the connection set.

What would settle it

A concrete finite abelian group G together with a connection set S such that the corresponding Cayley graph admits neither a perfect code nor a total perfect code, contrary to one of the proved statements.

Figures

Figures reproduced from arXiv: 2507.11871 by Peter J. Cameron, Roro Sihui Yap, Sanming Zhou.

Figure 1
Figure 1. Figure 1: shows the special case when p = 5, for which we have S = {(1, 1),(1, 4),(4, 1),(4, 4)} and Cay(Z5 ×Z5, S) admits C = ⟨(2, 1)⟩ = {(0, 0),(2, 1),(4, 2),(1, 3),(3, 4)} as a perfect code. ✷ (0,0) (1,1) (1,4) (4,4) (4,1) (2,1) (3,2) (3,0) (1,0) (1,2) (4,2) (0,3) (0,1) (3,1) (3,3) (1,3) (2,4) (2,2) (0,2) (0,4) (3,4) (4,0) (4,3) (2,3) (2,0) [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Cay(Z5 × Z10, S) admits C = ⟨(2, 1)⟩ as a total perfect code, where S = {(0, 5),(1, 4),(1, 6),(4, 4),(4, 6)}. The following theorem gives rise to [12, Theorem 1.4] in the special case when d = 1. Theorem 4.8. Let G be as in (2) and let S be an inverse-closed subset of G \ {(0, . . . , 0)} with ⟨S⟩ = G. Suppose that |S| = p l is a prime power such that p l | n but p l+1 ̸| n. Suppose further that exactly on… view at source ↗
read the original abstract

A perfect code in a graph $\Gamma = (V, E)$ is a subset $C$ of $V$ such that no two vertices in $C$ are adjacent and every vertex in $V \setminus C$ is adjacent to exactly one vertex in $C$. A total perfect code in $\Gamma$ is a subset $C$ of $V$ such that every vertex of $\Gamma$ is adjacent to exactly one vertex in $C$. In this paper we prove several results on perfect codes and total perfect codes in Cayley graphs of finite abelian groups.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript defines perfect codes (independent dominating sets with exact-one adjacency for non-code vertices) and total perfect codes (exact-one adjacency for all vertices) in graphs. It then proves several results on the existence, structure, and properties of such codes in Cayley graphs Cay(G,S) for finite abelian groups G and symmetric connection sets S with 0∉S.

Significance. If the proofs hold, the work adds concrete results to the literature on perfect codes in vertex-transitive graphs, exploiting the algebraic structure of abelian groups for explicit characterizations or constructions. This is a modest but useful contribution to combinatorial coding theory; the multiple claimed results and focus on both perfect and total-perfect variants are positive features.

major comments (2)
  1. [Introduction and statement of main results] The abstract and setup allow arbitrary symmetric S (0∉S). When the subgroup generated by S is proper, Cay(G,S) is disconnected. The paper must state explicitly whether theorems are proved under the standing assumption that <S>=G, or whether they are formulated componentwise; without this, global claims on code cardinality or existence do not hold in the disconnected regime.
  2. [Section on definitions and preliminary results] The local definitions of perfect and total perfect codes are standard, but the manuscript should verify that all stated theorems remain valid (or are restated) when the graph has multiple isomorphic components; otherwise the generality claimed for arbitrary S is overstated.
minor comments (2)
  1. [Introduction] Clarify the precise meaning of 'several results' by listing the main theorems with numbers in the introduction.
  2. [Notation and preliminaries] Ensure all notation for the group operation and the connection set S is introduced before first use and used consistently.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and for the constructive comments regarding the treatment of connectedness in Cayley graphs. We address the major comments point by point below and will revise the paper to incorporate the suggested clarifications.

read point-by-point responses

  1. Referee: [Introduction and statement of main results] The abstract and setup allow arbitrary symmetric S (0∉S). When the subgroup generated by S is proper, Cay(G,S) is disconnected. The paper must state explicitly whether theorems are proved under the standing assumption that <S>=G, or whether they are formulated componentwise; without this, global claims on code cardinality or existence do not hold in the disconnected regime.

    Authors: We agree that explicit clarification is needed. Our results on existence, structure, and cardinality are developed under the assumption that S generates G (making Cay(G,S) connected), as is standard in much of the literature on Cayley graphs to ensure the algebraic structure is fully exploited. In the revised manuscript we will add a standing assumption in the introduction and in the statements of the main theorems that <S> = G. We will also include a short remark explaining that when <S> is proper the graph consists of |G:<S>| isomorphic connected components, each a Cayley graph on the subgroup, and that perfect (resp. total perfect) codes may be constructed componentwise with the total cardinality scaling by the index. revision: yes

  2. Referee: [Section on definitions and preliminary results] The local definitions of perfect and total perfect codes are standard, but the manuscript should verify that all stated theorems remain valid (or are restated) when the graph has multiple isomorphic components; otherwise the generality claimed for arbitrary S is overstated.

    Authors: The definitions themselves are graph-theoretic and apply verbatim to disconnected graphs. However, we acknowledge that global statements (e.g., cardinality formulas or existence criteria phrased in terms of |G|) require care when the graph is disconnected. In the revision we will add a brief verification in the preliminary section: when the graph is disconnected the theorems hold componentwise, each component being isomorphic to Cay(<S>,S), and the overall code is the disjoint union of the codes on the components. We will restate the relevant theorems with this understanding or restrict them to the connected case via the standing assumption mentioned above. revision: yes

Circularity Check

0 steps flagged

No circularity; proofs derive from standard definitions and group properties

full rationale

The paper introduces standard definitions of perfect codes and total perfect codes as subsets satisfying local adjacency conditions, then proves existence and structural results for Cayley graphs Cay(G,S) on finite abelian groups G using group-theoretic arguments such as homomorphisms and coset partitions. No step reduces a claimed prediction or theorem to a fitted parameter, self-citation chain, or definitional tautology; the derivation chain remains independent of the target statements and relies on external mathematical facts about abelian groups and vertex-transitive graphs. The connectedness concern raised in the skeptic note is an assumption gap rather than a circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The results rest on standard definitions of graphs, Cayley graphs, and abelian groups; no free parameters or invented entities are indicated in the abstract.

axioms (2)
  • standard math Cayley graphs are defined via a finite abelian group and a connection set S with the usual left or right multiplication action.
    Invoked implicitly in the study of codes within these graphs.
  • standard math Finite abelian groups admit standard decompositions into cyclic components.
    Background fact used in analyzing symmetry for code existence.

pith-pipeline@v0.9.0 · 5617 in / 1237 out tokens · 35919 ms · 2026-05-22T00:22:22.892272+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages

  1. [1]

    Ahlswede, H

    R. Ahlswede, H. K. Aydinian and L. H. Khachatrian, On perfect codes and related concepts,Des. Codes Cryptogr.22 (2001), 221–237

    work page 2001

  2. [2]

    Araujo and I

    C. Araujo and I. Dejter, Lattice-like total perfect codes,Discuss. Math. Graph Theory34 (2014), no. 1, 57–74

    work page 2014

  3. [3]

    Biggs, Perfect codes in graphs,J

    N. Biggs, Perfect codes in graphs,J. Combin. Theory Ser. B15 (1973), 288–296

    work page 1973

  4. [4]

    Cowen, S

    R. Cowen, S. H. Hechler, J. W. Kennedy and A. Steinberg, Odd neighborhood transversals on grid graphs, Discrete Math. 307 (2007), 2200–2208

    work page 2007

  5. [5]

    I. J. Dejter, Perfect domination in regular grid graphs,Australas. J. Combin.42 (2008), 99–114

    work page 2008

  6. [6]

    I. J. Dejter and O. Serra, Efficient dominating sets in Cayley graphs,Discrete Appl. Math. 129 (2003), 319–328

    work page 2003

  7. [7]

    Deng, Efficient dominating sets in circulant graphs with domination number prime,Inform

    Y-P. Deng, Efficient dominating sets in circulant graphs with domination number prime,Inform. Process. Lett.114 (2014), 700–702

    work page 2014

  8. [8]

    Deng, Y-Q

    Y-P. Deng, Y-Q. Sun, Q. Liu and H.-C. Wang, Efficient dominating sets in circulant graphs,Discrete Math. 340(7) (2017), 1503–1507

    work page 2017

  9. [9]

    Dinitz, Full rank tilings of finite abelian groups,SIAM J

    M. Dinitz, Full rank tilings of finite abelian groups,SIAM J. Discrete Math.20 (2006), 160–170

    work page 2006

  10. [10]

    Etienne, Perfect codes and regular partitions in graphs and groups,European J

    G. Etienne, Perfect codes and regular partitions in graphs and groups,European J. Combin.8(1987), 139–144

    work page 1987

  11. [11]

    Etzion, Product constructions for perfect Lee codes,IEEE Trans

    T. Etzion, Product constructions for perfect Lee codes,IEEE Trans. Inform. Theory 57 (2011), 7473–7481

    work page 2011

  12. [12]

    R. Feng, H. Huang and S. Zhou, Perfect codes in circulant graphs,Discrete Math. 340 (2017), 1522–1527

    work page 2017

  13. [13]

    Ghidewon, R

    A-A. Ghidewon, R. H. Hammack and D. T. Taylor, Total perfect codes in tensor products of graphs, Ars Combin. 88 (2008), 129–134

    work page 2008

  14. [14]

    Hajós, Über einfache und mehrfache Bedeckung desn-dimensionalen Raumes mit einem Würfel- gitter, Math

    G. Hajós, Über einfache und mehrfache Bedeckung desn-dimensionalen Raumes mit einem Würfel- gitter, Math. Z. 47 (1941), 427–467

    work page 1941

  15. [15]

    Heden, A survey of perfect codes,Adv

    O. Heden, A survey of perfect codes,Adv. Math. Commun.2 (2008), 223–247

    work page 2008

  16. [16]

    Huang, B

    H. Huang, B. Xia, S. Zhou, Perfect codes in Cayley graphs,SIAM J. Discrete Math. 32 (2018), 548–559

    work page 2018

  17. [17]

    Jarvis,Algebraic Number Theory, Springer, Cham, 2014

    F. Jarvis,Algebraic Number Theory, Springer, Cham, 2014

    work page 2014

  18. [18]

    Knor and P

    M. Knor and P. Potočnik, Efficient domination in cubic vertex-transitive graphs,European J. Com- bin. 33 (2012), no. 8, 1755–1764

    work page 2012

  19. [19]

    Kratochvíl, Perfect codes over graphs,J

    J. Kratochvíl, Perfect codes over graphs,J. Combin. Theory Ser. B40 (1986), 224–228

    work page 1986

  20. [20]

    Kuziak, I

    D. Kuziak, I. Peterin and I. G. Yero, Efficient open domination in graph products,Discrete Math. and Theoret. Comp. Sci.16 (2014), no. 1, 105–120

    work page 2014

  21. [21]

    Y. S. Kwon, J. Lee, Perfect domination sets in Cayley graphs,Discrete Appl. Math. 162 (2014), 259–263

    work page 2014

  22. [22]

    Lee, Independent perfect domination sets in Cayley graphs,J

    J. Lee, Independent perfect domination sets in Cayley graphs,J. Graph Theory37 (2001), 213–219. 21

    work page 2001

  23. [23]

    Reji Kumar and G

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

    work page 2013

  24. [24]

    Martínez, R

    C. Martínez, R. Beivide and E. Gabidulin, Perfect codes for metrics induced by circulant graphs, IEEE Trans. Inform. Theory53 (2007), 3042–3052

    work page 2007

  25. [25]

    Obradović, J

    N. Obradović, J. Peters and G. Ružić, Efficient domination in circulant graphs with two chord lengths, Inform. Process. Lett.102 (2007), 253–258

    work page 2007

  26. [26]

    Rothaus and J

    O. Rothaus and J. G. Thompson, A combinatorial problem in the symmetric group,Pacific J. Math., 18 (1966), 175–178

    work page 1966

  27. [27]

    A. D. Sands, On the factorisation of finite abelian groups. II,Acta Mathematica Academiae Scien- tiarum Hungarica 13 (1962), no.1-2, 153–169

    work page 1962

  28. [28]

    Szabó, Factoring finite abelian groups by subsets with maximal span,SIAM J

    S. Szabó, Factoring finite abelian groups by subsets with maximal span,SIAM J. Discrete Math., 20 (2006), no. 4, 920–931

    work page 2006

  29. [29]

    Szabó and A

    S. Szabó and A. Sands,Factoring Groups into Subsets, CRC Press, Boca Raton, FL, 2009

    work page 2009

  30. [30]

    Terada, Perfect codes inSL(2, 2f), European J

    S. Terada, Perfect codes inSL(2, 2f), European J. Combin.25 (2004), 1077–1085

    work page 2004

  31. [31]

    NumberTheory Seminar Paris 1992-1993

    R. Tijdeman, Decomposition of the integers as a direct sum of two subsets, in: “NumberTheory Seminar Paris 1992-1993” (S. David, Ed.), pp. 261–276, Cambridge University Press, Cambridge, 1995

    work page 1992

  32. [32]

    J. H. van Lint, A survey of perfect codes,Rocky Mountain J. Math.5 (1975), 199–224

    work page 1975

  33. [33]

    D.T.Vuza, Supplementarysetsandregularcomplementaryunendingcanons(partone), Perspectives of New Music29 (2) (1991), 22–49

    work page 1991

  34. [34]

    Y. Wang, B. Xia and S. Zhou, Subgroup regular sets in Cayley graphs,Discrete Math. 345 (2022), no. 11, Paper No. 113023

    work page 2022

  35. [35]

    Zhou, Cyclotomic graphs and perfect codes,J

    S. Zhou, Cyclotomic graphs and perfect codes,J. Pure Appl. Algebra223 (2019), 931–947

    work page 2019

  36. [36]

    Zhou, Total perfect codes in Cayley graphs,Des

    S. Zhou, Total perfect codes in Cayley graphs,Des. Codes Cryptogr.81 (2016), 489–504. 22

    work page 2016