Recognizing circulant graphs in polynomial time: An application of association schemes (Q5940668)

A graph \(G\) is circulant iff there is a cyclic permutation of the vertex set of \(G\) which is an automorphism of \(G\). In this paper a polynomial recognition algorithm for certain classes of circulant graphs is presented (the problem is to decide whether \(G\) is a circulant graph or not). The method for recognizing circulant graphs is based on the notions of coherent configurations and Schur rings generated by graphs and on the interrelations between these notions when the graph \(G\) has a cyclic automorphism. The recognition problem for arbitrary circulant graphs is polynomially reducible to the recognition problem of circulant graphs induced by a generating set of the cyclic group which has trivial additive stabilizer. Geometric circulants and recursive geometric circulants are of special interest as models for interconnection networks.