×

zbMATH — the first resource for mathematics

On isomorphisms of finite Cayley graphs—a survey. (English) Zbl 1018.05044
This article is a systematic survey of various research directions concerning finite (directed) graphs and groups having the Cayley isomorphism property (shortly: CI-graphs and DCI-groups). Both theorems and examples are presented in a large number (only a few of them will be emphasized in what follows). The author calls a group \(G\) an \(m\)-DCI-group if all Cayley digraphs of valency at most \(m\) are CI-graphs; this notion can be modified (i) by replacing “at most” by “exactly”, and/or (ii) by restricting our attention to undirected graphs. The majority of the results stated are not proved in this paper.
After introducing some notions and exposing the problems, Section 2 contains several examples. Among them, it is shown that two Cayley graphs \(\text{Cay}(G_1, S_1)\) and \(\text{Cay}(G_2, S_2)\) may be isomorphic even if \(G_1\) and \(G_2\) are non-isomorphic groups. Furthermore, the representation of \(K_{m;d}\) (the complete \(d\)-partite graph such that each part has size \(m\)) as a Cayley graph is discussed.
Sections 3 and 4 are devoted to the study of CI-graphs. Let the theorem of Babai (given with proof) be sorted out from the results: \(\Gamma= \text{Cay}(G, S)\) is a CI-graph exactly if all regular subgroups of \(\text{Aut }\Gamma\) isomorphic to \(G\) are conjugate.
In Section 5 connected non-CI-graphs \(\Gamma= \text{Cay}(G,S)\) are constructed so that (iii) either \(G\) is a cyclic group of prime-power order, or (iv) \(S\) is a minimal generating system of \(G\). (In an example of type (iv), \(G\) coincides with the alternating group \(A_5\).)
Various graph classes are considered in Section 6, the CI-graphs are separated from the non-CI-graphs within these classes. We quote the theorem of Hirasaka and Muzychuk: All connected Cayley graphs of valency two of finite simple groups are CI-graphs.
Our attention is focussed on cyclic groups and circulant digraphs in Section 7. The theorem of Muzychuk is stated, it determines the numbers \(n\) for which the cyclic group \(Z_n\) is a DCI-group (or, respectively, a CI-group). The author’s theorem on the Sylow \(p\)-subgroups of the cyclic \(m\)-DCI-groups is recapitulated in a revised formulation.
In Section 8, DCI-groups and CI-groups are considered. A result of the author asserts that any finite CI-group is soluble. Another fact is that Muzychuk and Nowitz have found numbers \(n\) and \(p\) (prime) such that the elementary abelian group \(Z^n_p\) is not a CI-group. Finally, all the known CI-groups are explicitly listed.
The last two sections deal with \(m\)-DCI-groups and \(m\)-CI-groups.
A number of open problems is raised in the article. The bibliography consists of 121 items.

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures
20E99 Structure and classification of infinite or finite groups
PDF BibTeX XML Cite
Full Text: DOI