| Autor: |
Wang, Xiaomeng, Serra, Oriol, Xu, Shou-Jun, Zhou, Sanming |
| Rok vydání: |
2024 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
