Perfect codes in circulant graphs of degree $p^l-1$
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913253340217344 |
|---|---|
| author | Wang, Xiaomeng Serra, Oriol Xu, Shou-Jun Zhou, Sanming |
| author_facet | Wang, Xiaomeng Serra, Oriol Xu, Shou-Jun Zhou, Sanming |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_02205 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Perfect codes in circulant graphs of degree $p^l-1$ Wang, Xiaomeng Serra, Oriol Xu, Shou-Jun Zhou, Sanming Combinatorics 05C25, 05C69 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. |
| title | Perfect codes in circulant graphs of degree $p^l-1$ |
| topic | Combinatorics 05C25, 05C69 |
| url | https://arxiv.org/abs/2403.02205 |