Toida's Conjecture is True

Abstract

Let $S$ be a subset of the units in ${\bf Z_n}$. Let ${\Gamma}$ be a circulant graph of order $n$ (a Cayley graph of ${\bf Z_n}$) such that if $ij\in E({\Gamma})$, then $i - j$ (mod $n$) $\in S$. Toida conjectured that if $\Gamma'$ is another circulant graph of order $n$, then ${\Gamma}$ and ${\Gamma '}$ are isomorphic if and only if they are isomorphic by a group automorphism of ${\bf Z_n}$ In this paper, we prove that Toida's conjecture is true. We further prove that Toida's conjecture implies Zibin's conjecture, a generalization of Toida's conjecture.