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

  • Mikhail E. Muzychuk
  • Gottfried Tinhofer
DOI: https://doi.org/10.37236/1570

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.

Published
2001-05-26
Issue
Volume 8, Issue 1 (2001)
Article Number
R26