Recognizing circulant graphs of prime order in polynomial time

Mikhail E. Muzychuk ; Gottfried Tinhofer

The electronic journal of combinatorics, Tome 5 (1998)

Résumé

A circulant graph $G$ of order $n$ is a Cayley graph over the cyclic group ${\bf Z}_n.$ Equivalently, $G$ is circulant iff its vertices can be ordered such that the corresponding adjacency matrix becomes a circulant matrix. To each circulant graph we may associate a coherent configuration ${\cal A}$ and, in particular, a Schur ring ${\cal S}$ isomorphic to ${\cal A}$. ${\cal A}$ can be associated without knowing $G$ to be circulant. If $n$ is prime, then by investigating the structure of ${\cal A}$ either we are able to find 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$.

Détail

DOI : 10.37236/1363

Classification : 05C25, 05C85, 05E30
Mots-clés : recognition algorithm, circulant graph, cyclic association scheme