The isomorphism problem for circulant graphs via Schur ring theory (Q2717209)

In this article a rich overview of known results is contained and some interesting new theorems are shown. A broad exposition of the genesis of the isomorphy problem of circulant graphs is given and, as a generalization of this, the investigations of \textit{L. Babai} [Acta Math. Acad. Sci. Hung. 29, 329-336 (1977; Zbl 0378.05035)] about the CI (Cayley isomorphy) property of combinatorial structures are touched.NEWLINENEWLINENEWLINEThis branch of research started with the reviewer's conjecture on the isomorphy of circulant graphs, namely, that a necessary and sufficient condition of isomorphy is that the connection sets are conjugate by a multiplier which is relatively prime to the number \(n\) of vertices. The necessity of this condition turned out to be false if \(n\) is divisible by \(8\) or by an odd prime square. Later Muzychuk proved the validity of the criterion for every other value of \(n\) [see \textit{M. Muzychuk}, J. Comb. Theory, Ser. A 72, No. 1, 118-134 (1995; Zbl 0833.05063), Discrete Math. 167/168, 497-510 (1997; Zbl 0877.05040) and Discrete Math. 176, No. 1-3, 285-298 (1997; Zbl 0885.05090)].NEWLINENEWLINENEWLINEThe following question remained open: what is the criterion of isomorphy for the ``bad'' \(n\)'s? Concerning this subject, the authors mention an unpublished conjecture of Zibin which is a generalized form of an earlier conjecture of \textit{S. Toida} [J. Comb. Theory, Ser. B 23, 239-246 (1977; Zbl 0386.05028)]. After this, the authors deal with Schur rings (certain subalgebras of the group algebras of the form \(\mathbb{Q} H\) where \(\mathbb{Q}\) is the ring of rationals and \(H\) is a finite group), including their connections with Cayley graphs and permutation groups. A special emphasis is given to Schur rings over cyclic groups. The authors prove the conjecture of Zibin (using the technique of Schur rings), and, as an application of this, they give a new treatment of the isomorphism problems of double-loop circulants (of the circulants which are, in essence, regular undirected graphs of degree 2) and of the ciculants having eight vertices. Zibin's conjecture is the following: Let \(S\) and \(T\) be the connection sets of two circulant graphs with \(n\) vertices. For any divisor \(d\) of \(n\), \((S)_d\) denote the set of numbers \(x\in S\) such that the greatest common divisor of \(x\) and \(n\) is \(d\). Then the graphs are isomorphic only if there are numbers \(m_d\) such that \(m_d(S)= (T)_d\pmod n\), where \(d\) runs through the divisors of \(n\) and the \(m_d\)'s are relatively prime to \(n\). In addition, an analogon (for the Cayley association schemes) of an important theorem of Babai on CI-subsets of groups is verified.NEWLINENEWLINENEWLINEFrom the authors' abstract: ``The concluding section contains a short historical and bibliographical survey of various results related to the isomorphism problem for Cayley graphs.''NEWLINENEWLINENEWLINEThe classification problem of all CI-groups is mentioned as a very noteworthy open question. The list of references consists of ninety items.NEWLINENEWLINEFor the entire collection see [Zbl 0960.00079].