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}[ζ_m]/A$, with connection sets $\{\pm (ζ_m^i + A): 0 \le i \le m-1\}$ and $\{\pm (ζ_m^i + A): 0 \le i \le ϕ(m) - 1\}$, respectively, where $ζ_m$ ($m \ge 2$) is an $m$th primitive root of unity, $A$ a nonzero ideal of $\mathbb{Z}[ζ_m]$, and $ϕ$ 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}(A)$, respectively. We give a necessary and sufficient condition for $D/A$ to be a perfect $t$-code in $G^*_{m}(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}[ζ_m]$ containing $A$. In the case when $m = 3, 4$, $G_m((α))$ is known as an Eisenstein-Jacobi and Gaussian networks, respectively, and we obtain necessary conditions for $(β)/(α)$ to be a perfect $t$-code in $G_m((α))$, where $0 \ne α, β\in \mathbb{Z}[ζ_m]$ with $β$ dividing $α$. 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