Cyclotomic graphs and perfect codes

Abstract

We study two families of cyclotomic graphs and perfect codes in them. They are Cayley graphs on the additive group of $\mathbb{Z}[{\zeta }_m]/A$, with connection sets $\{\pm ({\zeta }_m^i+A):0\le i\le m-1\}$ and $\{\pm ({\zeta }_m^i+A):0\le i\le \varphi (m)-1\}$, respectively, where ${\zeta }_m$ ($m\ge 2$) is an $m$th primitive root of unity, $A$ a nonzero ideal of $\mathbb{Z}[{\zeta }_m]$, and $\varphi$ Euler's totient function. We call them the $m$th cyclotomic graph and the second kind $m$th cyclotomic graph, and denote them by $G_m(A)$ and $G_m^{\ast }(A)$, respectively. We give a necessary and sufficient condition for $D/A$ to be a perfect $t$-code in $G_m^{\ast }(A)$ and a necessary condition for $D/A$ to be such a code in $G_m(A)$, where $t\ge 1$ is an integer and $D$ an ideal of $\mathbb{Z}[{\zeta }_m]$ containing $A$. In the case when $m=3,4$, $G_m((\alpha ))$ is known as an Eisenstein-Jacobi and Gaussian networks, respectively, and we obtain necessary conditions for $(\beta )/(\alpha )$ to be a perfect $t$-code in $G_m((\alpha ))$, where $0\ne \alpha ,\beta \in \mathbb{Z}[{\zeta }_m]$ with $\beta$ dividing $\alpha$. In the literature such conditions are known to be sufficient when $m=4$ and $m=3$ under an additional condition. We give a classification of all first kind Frobenius circulants of valency $2p$ and prove that they are all $p$th cyclotomic graphs, where $p$ is an odd prime. Such graphs belong to a large family of Cayley graphs that are efficient for routing and gossiping.

Journal of Pure and Applied Algebra, 2018

References in corpus (2)

• Perfect codes in circulant graphs
• Rotational circulant graphs

Cited by in corpus (6)

• Perfect codes in circulant graphs
• Corrigendum to "On subgroup perfect codes in Cayley graphs" [European J. Combin. 91 (2021) 103228]
• Subgroup regular sets in Cayley graphs
• On subgroup perfect codes in Cayley graphs
• Perfect codes in Cayley sum graphs
• On non-normal subgroup perfect codes