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

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.