Recognizing Circulant Graphs in Polynomial Time: An Application of Association Schemes

Mikhail E. Muzychuk, Gottfried Tinhofer


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.

Full Text: