On symmetries of Cayley graphs and the graphs underlying regular maps

By definition, Cayley graphs are vertex-transitive, and graphs underlying regular or orientably-regular maps (on surfaces) are arc-transitive. This paper addresses questions about how large the automorphism groups of such graphs can be. In particular, it is shown how to construct 3-valent Cayley graphs that are 5-arc-transitive (in answer to a question by Cai Heng Li), and Cayley graphs of valency 3' + 1 that are 7-arc-transitive, for all t > 0. The same approach can be taken in considering the graphs underlying regular or orientably-regular maps, leading to classifications of all such maps having a 1-, 4- or 5-arc-regular 3-valent underlying graph (in answer to questions by Cheryl Praeger and Sanming Zhou). (C) 2008 Elsevier Inc. All rights reserved.