Recognizing Circulant Graphs of Prime Order in Polynomial Time

Abstract

A circulant graph $G$ of order $n$ is a Cayley graph over the cyclic group ${\bf Z}_n.$ Equivalently, $G$ is circulant iff its vertices can be ordered such that the corresponding adjacency matrix becomes a circulant matrix. To each circulant graph we may associate a coherent configuration ${\cal A}$ and, in particular, a Schur ring ${\cal S}$ isomorphic to ${\cal A}$. ${\cal A}$ can be associated without knowing $G$ to be circulant. If $n$ is prime, then by investigating the structure of ${\cal A}$ either we are able to find an appropriate ordering of the vertices proving that $G$ is circulant or we are able to prove that a certain necessary condition for $G$ being circulant is violated. The algorithm we propose in this paper is a recognition algorithm for cyclic association schemes. It runs in time polynomial in $n$.