Some results on perfect codes in Cayley sum graphs

Masoumeh Koohestani, Doost Ali Mojdeh, Mohsen Ghasemi Hassan Khodaiemehr · 2025

Read Some results on perfect codes in Cayley sum graphs by Masoumeh Koohestani, Doost Ali Mojdeh, Mohsen Ghasemi Hassan Khodaiemehr (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-2505-03952.txt.

Introduction

Masoumeh Koohestani and three co-authors prove a result about perfect codes inside a kind of network built from a group in a 2025 paper. In such a Cayley sum graph, each node links to others by set sums of group members. A perfect code is a set of nodes placed so that every node sits next to exactly one code node, a spread with no waste. The authors give a clean necessary and sufficient test for when a normal subgroup of a finite group forms such a code.

Catalog record

CREATORMasoumeh Koohestani, Doost Ali Mojdeh, Mohsen Ghasemi Hassan Khodaiemehr
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE26 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-03952

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Some results on perfect codes in Cayley sum graphs Masoumeh Koohestani, Doost Ali Mojdeh, Mohsen Ghasemi Hassan Khodaiemehr Abstract This paper explores perfect codes within the context of Cayley sum graphs. We establish a necessary and sufficient condition for a normal subgroup of a finite group to be a subgroup perfect code and another necessary and sufficient condition for a normal subgroup not to be a subgroup perfect code. These results enable us to identify relationships between perfect codes of a group and its quotient groups. Furthermore, we examine a special nonabelian group, V 8 ​ n V_{8n} , and identify its possible connected Cayley sum graphs, as well as their corresponding subgroup perfect codes and subgroup total perfect codes. Keywords: Cayley sum graph, normal subgroup, perfect code AMS Mathematics Subject Classification (2020): 05C25, 05C69, 94B99 † † E-mail Addresses : [email protected], [email protected], [email protected], [email protected] 1 Introduction Perfect codes have played a pivotal role in information theory ever since the advent of coding theory in the late 1940s. Refer to surveys [ 8 , 16 ] for a comprehensive collection of results on perfect codes. The significance of perfect codes is widely acknowledged, with Hamming and Golay codes being noteworthy examples. The concept of perfect codes can be extended to graphs in a natural manner [ 2 ] . Within the context of graphs, perfect codes are also known as efficient dominating sets [ 7 , 11 ] or independent perfect dominating sets [ 12 ] . Perfect codes in Cayley graphs have garnered significant attention, as evidenced by recent research in the field [ 4 , 14 , 19 , 22 ] . For a group G with the identity element 1 and an inverse-closed subset of G\setminus\{1\} like X (that is, X^{-1}:=\{x^{-1}~|~x\in X\}=X ), the Cayley graph {\rm{Cay(G,X)}} of G with the connection set X is a graph whose vertex set is G and two elements x,y\in G are adjacent if and only if yx^{-1}\in X . In [ 9 ] , Huang et al. introduced the following concept: A subset C of a group G is called a perfect code of G if there exists a Cayley graph {\rm Cay}(G,X) of G which admits C as a perfect code. Of particular interest are perfect codes in Cayley sum graphs, which have drawn considerable attention from researchers. Cayley sum graphs, also referred to as addition graphs [ 3 ] , addition Cayley graphs [ 6 , 12 , 18 ] , and sum graphs [ 5 ] , are variations of Cayley graphs. The concept of Cayley sum graphs, initially developed for abelian groups, was later generalized for arbitrary groups in [ 1 ] . Numerous authors have conducted research on Cayley sum graphs, contributing to the body of knowledge in this area (see [ 13 , 15 , 20 ] ). This paper builds upon this foundation by exploring perfect codes in Cayley sum graphs. Let \Gamma be a graph with vertex set V(\Gamma) and edge set E(\Gamma) . A perfect code in \Gamma is a subset C of V(\Gamma) such that no two vertices in C are adjacent and every vertex in V(\Gamma)\setminus C is adjacent to exactly one vertex in C . Also, C is called a total perfect code in \Gamma , if every vertex in V(\Gamma) has exactly one neighbor in C . Let G be a group. An element x of G is called a square if x=y^{2} for some element y\in G . A subset of G is called a square-free subset of G if it is a set without squares. A subset X of G is called a normal subset if X is a union of some conjugacy classes of G or equivalently, for every g\in G , g^{-1}Xg:=\{g^{-1}xg:x\in X\}=X . Remark that any subset of an abelian group is normal. Let X be a a normal subset of G . The Cayley sum graph {\rm CS}(G,X) of G with respect to the connection set X is a graph whose vertex set is G and two vertices g and h being adjacent if and only if gh\in X and g\neq h . A perfect code (total perfect code) of {\rm CS}(G,X) which is also a subgroup of G is called a subgroup perfect code ( subgroup total perfect code ) of G . A subgroup perfect code (subgroup total perfect code) H of the group G is said to be nontrivial when H\neq\{1\} . Also, the set of all perfect codes (total perfect codes) of {\rm CS}(G,X) is denoted by \mathcal{P}(G,X) ( \mathcal{T}(G,X) ). Additionally, it is obvious that the neighborhood of a vertex g is Xg^{-1} if g^{2}\notin X and (X\setminus\{g^{2}\})g^{-1} if g^{2}\in X . Therefore {\rm CS}(G,X) is a regular graph if and only if either X is square-free in G or X consists of all squares of G . In what follows, we summarize the main points that we will cover in this paper. In Section 2 , we present necessary and sufficient conditions for a subgroup of a finite group to be a subgroup perfect code, drawing interesting connections between subgroup perfect codes of a group and those of its quotient group. Section 3 is dedicated to identifying perfect codes and total perfect codes within the renowned group V_{8n} . Detailed computational methods employed to define Cayley sum graphs and discover their perfect codes are discussed in Section 4 . 2 Subgroup Perfect Codes In this section, we begin by confirming a fundamental fact about perfect codes in Cayley sum graphs. We then present and prove a necessary and sufficient condition for a normal subgroup of a group to be, as well as not be, a subgroup perfect code of that group. Notably, we use these results to prove a statement that reveals the relationship between the subgroup perfect codes of a group and its quotient group. A similar statement for quotient groups was previously demonstrated in the context of Cayley graphs in [ 21 ] . Prior to delving into the results, we recall a necessary and sufficient condition for a subgroup of a given group to be a subgroup perfect code. Lemma 1 . [ 20 , Lemma 3.1] Let G be a group and H a subgroup of G . Then H is a subgroup perfect code of G if and only if G has a normal subset X such that X\cup\{1\} is a left transversal of H in G . Lemma 2 . Let G be a group and H a subgroup of G . Then H is a subgroup perfect code of some Cayley sum graph of G if and only if it is a subgroup perfect code of any subgroup of G which contains H . Proof. It is sufficient to prove the necessity. Suppose that H\in\mathcal{P}(G,X) , for some normal subset X of G . By Lemma 1 , X\cup\{1\} is a left transversal of H in G which follows that every g\in G\setminus H can be uniquely written as g=xh^{-1}, (1) for some x\in X and h\in H . Let K be an arbitrary subgroup of G such that H\subseteq K . From ( 1 ), every k\in

Read the complete text