Cyclotomic graphs, perfect codes and Frobenius circulants of valency $2p$ or $2p^2$

Sanming Zhou

Published 2015-02-11Version 1

Let $\zeta_m$ ($m \ge 2$) be an $m$th primitive root of unity and $A$ a nonzero ideal of $\mathbb{Z}[\zeta_m]$. We define the $m$th cyclotomic graph $G_{m}(A)$ to be the Cayley graph on the additive group of $\mathbb{Z}[\zeta_m]/A$ such that $\alpha + A, \beta + A \in \mathbb{Z}[\zeta_m]/A$ are adjacent if and only if $(\alpha-\beta) + A = \zeta_m^i + A$ or $-\zeta_m^i + A$ for some $i$. With motivation from constructing perfect codes as well as interconnection networks efficient for information transmission, in this paper we study cyclotomic graphs and their connections with two families of Frobenius circulant graphs. We prove that full-valent cyclotomic graphs are arc-transitive and also rotational if in addition $m$ is odd. We give a necessary and sufficient condition for $D/A$ to be a perfect $t$-error-correcting code in $G_{m}(A)$, where $D$ is an ideal of $\mathbb{Z}[\zeta_m]$ containing $A$ and $t \ge 1$ is an integer. In particular, in the case $m=2,3$ we obtain necessary and sufficient conditions for $(\beta)/(\alpha)$ to be a perfect $t$-error-correcting code in the Gaussian or Eisenstein-Jacobi network $G_m((\alpha))$, where $0 \ne \alpha, \beta \in \mathbb{Z}[\zeta_m]$ with $\beta$ dividing $\alpha$. We classify first-kind Frobenius circulants of valency $2p$ or $2p^2$, where $p$ is a prime, and prove that they are $p$th or $p^2$th cyclotomic graphs, respectively.