Subgroup perfect codes of S n S_{n} in Cayley sum graphs
Ankan Shaw, Biswajit Mondal, Satya Bagchi · 2025
Read Subgroup perfect codes of S n S_{n} in Cayley sum graphs by Ankan Shaw, Biswajit Mondal, Satya Bagchi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-05069.txt.
Introduction
Perfect codes in Cayley sum graphs ask whether a subgroup can tile a group perfectly by adjacency. Ankan Shaw, lead author with two co-authors, study that question for symmetric and alternating groups in a 2025 algebra paper. A perfect code is a set of vertices no two adjacent, with every other vertex adjacent to exactly one code vertex.
The authors prove no proper subgroup of the symmetric group forms such a perfect code. Using that result, they give a complete characterisation of subgroup perfect codes for the alternating group. The work settles which subgroups can serve as perfect codes in this graph family.
Catalog record
| CREATOR | Ankan Shaw, Biswajit Mondal, Satya Bagchi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-05069
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Subgroup perfect codes of S n S_{n} in Cayley sum graphs Ankan Shaw, Biswajit Mondal, Satya Bagchi Abstract A perfect code in a graph Γ = ( V , E ) \Gamma=(V,E) is a subset C C of V V such that no two vertices in C C are adjacent, and every vertex in V ∖ C V\setminus C is adjacent to exactly one vertex in C C . Let G G be a finite group, and let S S be a square-free normal subset of G G . The Cayley sum graph of G G with respect to S S is a simple graph with vertex set G G and two vertices x x and y y are adjacent if x y ∈ S . xy\in S. A subset C C of G G is called perfect code of G G if there exists a Cayley sum graph of G G that admits C C as a perfect code. In particular, if a subgroup of G G is a perfect code of G G , then the subgroup is called a subgroup perfect code of G G . In this work, we prove that there does not exist any proper perfect subgroup code of symmetric group S n S_{n} . Using this result, we provide a complete characterization of the perfect subgroup code of the alternating group A n A_{n} . 2021 \normalbaroutside MSC Classification]05C25, 05C69, 94B99, 20B30, 20D06 keywords Cayley sum graph, Perfect code, Subgroup perfect code, Symmetric group, Alternating group pacs [ † † equal-contributors: These authors contributed equally to this work. † † equal-contributors: These authors contributed equally to this work. † † equal-contributors: These authors contributed equally to this work. † † equal-contributors: These authors contributed equally to this work. 1 Introduction Every group and every graph considered in the study are finite. In this work, we use conventional group-theoretic vocabulary and notation, which are available, for instance, in Huang2018 ; Suzuki19821 . Let \Gamma be a graph with edge set E(\Gamma) and vertex set V(\Gamma) . If there is no path in \Gamma connecting two vertices, the distance in \Gamma between them is equal to \infty . Otherwise, it equals the shortest path length between the two vertices. Let t be a natural number and C be a subset of V(\Gamma) . If every vertex of \Gamma is at a distance no greater than t from precisely one vertex in C , then C Chen2020 ; Krotov2020 is said to be a perfect t -code in \Gamma . A perfect code is generally a perfect 1 -code. In equivalent terms, if C is an independent set of \Gamma and each vertex in V(\Gamma)\setminus C is adjacent to precisely one vertex in C , then subset C of V(\Gamma) is a perfect code in \Gamma . A perfect code in a graph is also referred to as an efficient dominating set Dejter2003 ; Lee2001 of the graph. Let G be a finite group and S be a normal subset of G (i.e., g^{-1}Sg=S for all g\in G ). Note that in an abelian group, every subset is automatically normal. An element g\in G is called a square if there exists h\in G such that g=h^{2} . A subset of G is said to be square-free if it contains no square elements. Given a subset S\subseteq G , the Cayley sum graph CayS(G,S) is defined as the directed graph whose vertex set is G , with two vertices x and y connected by an edge if and only if xy\in S . When S is normal, the graph becomes undirected since the condition xy\in S is equivalent to yx\in S . Furthermore, if there exists g\in G such that g^{2}\in S , then \{g,g\} forms a semi-edge (an edge with a single endpoint). The graph is called simple if it contains neither multiple edges nor semi-edges. Initially, Biggs Biggs1973 made known the concept of perfect t -codes in a graph. He defined perfect t -codes under the Hamming and Lee metrics as a generalization. Perfect codes in Cayley graphs have been extensively studied; see Huang2018 for a survey of early results and Ma ; Zhang2021 ; Zhang2022 ; Zhang2023 ; Zhang24 for recent advances in this area. In MacWilliams1977 , the authors showed that the Hamming distance of two code words of length n over an alphabet of size m>1 corresponds precisely to the graph distance in the Hamming graph H(n,m) . Thus, under the Hamming metric, perfect t -codes in H(n,m) are precisely those defined in the classical context. Similarly to this, the graph distance in the Cartesian product L(n,m) of n copies of the cycle of length m equals the Lee distance Horak between words of length n across an alphabet of size m>2 . Note that all graphs considered in this paper are simple. Thus, we always consider a simple Cayley sum graph CayS(G,S) , that is, the connecting set S needs to be normal and square-free. More explicitly, for a square-free normal subset S of G , the Cayley sum graph CayS(G,S) of G with respect to the connecting set S is a simple graph with vertex set G and two vertices x and y are adjacent if xy\in S . The notion of Cayley sum graphs was initially introduced for abelian groups before being extended to arbitrary groups in Amo . In 1989 , Chung Chung first introduced the Cayley sum graphs of abelian groups. As pointed out in Gry , the twins of the usual Cayley graphs, Cayley sum graphs are rather difficult to study, so that they received much less attention in the literature. Most results on Cayley sum graphs can be found in Amo ; Che ; ev ; Kon ; Lev ; Ma2016 . In Ma2020 , authors studied perfect codes of Cayley sum graphs and define a subgroup perfect code of a group by using Cayley sum graphs instead of Cayley graphs. More precisely, a subgroup perfect code of a group G is a subgroup of G and a perfect code of some Cayley sum graph of G. They gave a necessary and sufficient condition for a non-trivial subgroup of an abelian group with non-trivial Sylow 2 -subgroup to be a subgroup perfect code of the group. In very recently, J Zhang Zhang2024 gave a necessary conditions of a subgroup of a given group being a (total) perfect code in a Cayley sum graph of the group. In there, the Cayley sum graphs of some families of groups which admit a subgroup as a (total) perfect code are classified. In this paper, we extend this study to the symmetric group S_{n} , examining subgroup perfect codes in its Cayley sum graph. As a key application of our results, we further explore perfect subgroup codes in the alternating group A_{n} . Our work provides a complete classification of subgroup perfect codes for both S_{n} and A_{n} in the Cayley sum graph setting, contributing new structural insights into coding theory in non-abelian groups. Excluding the introductory part, the present work is demarcated into two sections. Section 2 lays the groundwork by presenting essential definitions, established results, and