2024/03/04 by Xiaomeng Wang, Oriol Serra, Wang, Xiaomeng +5
Computer Science · Engineering · #05C25 #05C69 #Coding theory and cryptography #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2403.02205
openalex publication_date 2024/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A perfect code in a graph is an independent set of the graph such that every vertex outside the set is adjacent to exactly one vertex in the set. A circulant graph is a Cayley graph of a cyclic group. In this paper we study perfect codes in circulant graphs of degree pl - 1, where p is a prime and l ≥ 1. We obtain a necessary and sufficient condition for such a circulant graph to admit perfect codes, give a construction of all such circulant graphs which admit perfect codes, and prove a lower bound on the number of distinct perfect codes in such a circulant graph. This extends known results for the case l=1 and provides insight on the general problem on the existence and structure of perfect codes in circulant graphs.