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

Mikhail E. Muzychuk, Gottfried Tinhofer

Abstract


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: PDF