Isomorphism Testing for Circulant Graphs

In this paper we focus on connected directed/undirected circulant graphs $C_n(a,b)$. We investigate some topological characteristics of the graphs, and define a simple combinatorial model for them, which is new for the topic. Building on such a model, we derive a necessary and sufficient condition to test, in $O(\log^2n)$ time, whether two circulant graphs $C_n(a,b)$ and $C_n(a',b')$ are isomorphic or not. The method is entirely elementary and consists of comparing two suitably computed integers in $\{1, \dots, \frac{n}{\gcd(n,a)\gcd(n,b)}-1\}$, and of verifying if $\{\gcd(n,a),\gcd(n,b)\}=\{\gcd(n,a'),\gcd(n,b')\}$. It also allows for building the mapping function in linear time. As a by-product we get an alternative proof of the validity of \'Ad\'am's conjecture on all the $C_n(a,b)$'s. In addition, simple methods are proposed for computing the positive integer that, given two isomorphic circulant graphs, ``transforms'' one of them into the other one, and for generating all the circulant graphs isomorphic to a given one.