×

The isomorphism problem for circulant graphs via Schur ring theory. (English) Zbl 0979.05079

Barg, Alexander (ed.) et al., Codes and association schemes. DIMACS workshop, DIMACS Center, Princeton, NJ, USA, November 9-12, 1999. Providence, RI: AMS, American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 56, 241-264 (2001).
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 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.
This 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 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)].
The 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 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.
From the authors’ abstract: “The concluding section contains a short historical and bibliographical survey of various results related to the isomorphism problem for Cayley graphs.”
The classification problem of all CI-groups is mentioned as a very noteworthy open question. The list of references consists of ninety items.
For the entire collection see [Zbl 0960.00079].

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05E30 Association schemes, strongly regular graphs
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures
PDFBibTeX XMLCite