On isomorphisms of finite Cayley graphs—a survey.

*(English)*Zbl 1018.05044This 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.

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.

Reviewer: András Ádám (Budapest)

##### 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 |