Recognizing Circulant Graphs in Polynomial Time: An Application of Association Schemes
Mikhail E. Muzychuk, Gottfried Tinhofer · The Electronic Journal of Combinatorics · 2001
In this paper we present a time-polynomial recognition algorithm for certain classes of circulant graphs. Our approach uses coherent configurations and Schur rings generated by circulant graphs for elucidating their symmetry properties and eventually finding a cyclic automorphism.