On isomorphisms of finite Cayley graphs---a survey (Q1849934)

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.