1. Perfect codes in circulant graphs of degree $p^l-1$
- Author
-
Wang, Xiaomeng, Serra, Oriol, Xu, Shou-Jun, and Zhou, Sanming
- Subjects
Mathematics - Combinatorics ,05C25, 05C69 - Abstract
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 $p^l - 1$, where $p$ is a prime and $l \ge 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.
- Published
- 2024