Paper Info
Title
Recognizing circulant graphs of prime order in polynomial time
Abstract
A circulant graph G of order n is a Cayley graph over the cyclic group Zn: Equivalently, G is circulant i its vertices can be ordered such that the cor- responding adjacency matrix becomes a circulant matrix. To each circulant graph we may associate a coherent congurationA and, in particular, a Schur ringS isomorphic toA. A can be associated without knowing G to be circu- lant. If n is prime, then by investigating the structure ofA either we are able to nd an appropriate ordering of the vertices proving that G is circulant or we are able to prove that a certain necessary condition for G being circulant is violated. The algorithm we propose in this paper is a recognition algorithm for cyclic association schemes. It runs in time polynomial in n.
Year
Venue
Keywords
1998
Electr. J. Comb.
recognition algorithm,circulant graph,cyclic association scheme,association scheme,circulant matrix,adjacency matrix,polynomial time,cyclic group,cayley graph
Field
DocType
Volume
Adjacency matrix,Prime (order theory),Discrete mathematics,Association scheme,Combinatorics,Circulant graph,Cyclic group,Vertex (geometry),Cayley graph,Circulant matrix,Mathematics
Journal
5
Citations 
PageRank 
References 
16
1.50
2
Authors
2
Name
Order
Citations
PageRank
Mikhail Muzychuk117125.28
Gottfried Tinhofer211220.81