Automorphism Groups of Cayley Maps 

A Cayley graph has vertex set the elements of a group G and edge set determined by a balanced generating set X. A Cayley map M is an embedding of a Cayley graph in an oriented surface such that the local rotation at each vertex is described by the same permutation p of X.

Question: Given a finite group G, is there a Cayley map M for which the full automorphism group AutM is isomorphic to G?

Any finite group G ``lives inside'' AutM for any Cayley map M=CM(G,X,p) based on G. It is the adjective ``full'' that keeps the above question interesting. The Klein four-group, for example, is not the full automorphism group of any Cayley map.

The inner structure of automorphism groups of Cayley maps has been described in Theorem 4 of [J1] using the concept of a special graph-automorphism rho. Let M=CM(G,X,p). The full automorphism group AutM of M is isomorphic to the group (G x <rho>, o), where the binary operation o is defined as (a, rho^m) o (b, rho^n) = (a rho^m(b), theta), and theta is a power of rho satisfying the property theta(c) = rho^m(b)^{-1} rho^m(b rho^n(c)), for all a,b,c in G.

Automorphism groups of Cayley maps are not semidirect products in general ( rho is not bound to be a group automorphism, in the first place), despite their obvious similarity. They are a special case of the more general rotary product described in [J2].

Based on this structural description, we obtain an immediate corollary toward the characterization of automorphism groups of Cayley maps. A graphical regular representation of group G is a Cayley graph Gamma =C(G,X) whose full automorphism group Aut Gamma is isomorphic to G. Any graph automorphism of Gamma which fixes a vertex is trivial. This simplifies the structure of the automorphism group of any Cayley map CM(G,X,p) based on Gamma and, in fact, makes it isomorphic to G. Thus, any finite group G possessing a graphical regular representation Gamma is the full automorphism group of any Cayley map M based on Gamma.

All the finite groups with graphical regular representation have been identified. A nice overview of this topic can be found in [G]. There are only two infinite classes and 13 sporadic cases of finite groups (the Klein group among them) that do not have a graphical regular representation. These are the cases whose structure has to be studied in order to complete the characterization of automorphism groups of Cayley maps.


[G] C.D. Godsil, GRR's for non-solvable groups, Algebraic Methods in Graph Theory, vol.1, (L. Lovasz and T. Sos eds.), North-Holland 1981.

[J1] R.Jajcay, Automorphism Groups of Cayley Maps, Journal of Comb. Theory Series B 59 (1993) 297-310.

[J2] R.Jajcay, On a New Product of Groups, Europ. J. Combinatorics 15 (1994) 251-252.

Submitted by: Robert Jajcay

Send comments to and

August, 1995