On the isomorphism problem of Cayley graphs
by
Péter P. Pálfy
Eötvös University, Budapest

Let G be a finite group and S a subset of G with S^-1=S. Then the Cayley graph Cay(G, S) has vertex set G and edges (g, gs) for all g in G and s in S. Obviously, if a is an automorphism of the group G, then the Cayley graphs Cay(G, S) and Cay(G, S^a) are isomorphic. The question arises, whether the converse is true, i.e., if Cay(G, S) and Cay(G, T) are isomorphic graphs then there exists a group automorphism a such that T=S^a. We say that a group G is a CI-group, if this Cayley Isomorphism property holds for any pair of isomorphic Cayley graphs of G. This problem for cyclic groups, i.e., for circulant graphs was formulated by András Ádám in 1967, but it has been solved only recently by Michail Muzychuk. In the general case Cai-Heng Li proved that every CI-group is solvable. However, it is not known, for example, whether the elementary abelian p-groups of odd order are CI-groups or not. (In 1992 L. A. Nowitz constucted an example showing that Z₂⁶ is not a CI-group.) In a joint work in progress with Cai-Heng Li we give further restricitions on the structure of the possible CI-groups.

Date received: February 11, 2000