## Arc-transitive non-Cayley graphs from regular maps.(English)Zbl 0824.05030

A map $$M$$ in an orientable 2-manifold is said to be orientably regular when $$\operatorname{Aut}(M)$$ acts transitively and fixed-point-free on the set $$D$$ of all oriented edges of its underlying graph $$G$$. (Note that $$| D|/2$$ is the number of edges of $$G$$.) In this case there exist $$p$$ and $$r$$ such that $$G$$ is $$r$$-valent and each face of $$M$$ is bounded by a closed walk of length $$p$$; $$M$$ is then said to be of type $$\{p, r\}$$. The main result is that, if $$M$$ is orientably regular of type $$\{p, r\}$$ where $$r\geq 3$$ and $$p$$ is a prime such that $$p> r (r- 1)$$, then $$G$$ is not a Cayley graph. The proof relies interestingly upon a preliminary result enumerating closed oriented walks of length $$p$$ rather than upon the usual technique of proving nonexistence of a regular subgroup of $$\operatorname{Aut}(G)$$. From this the authors deduce that for each $$r\geq 3$$, there exist infinitely many arc-transitive $$r$$-valent graphs that are not Cayley graphs.

### MSC:

 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) 05C10 Planar graphs; geometric and topological aspects of graph theory 05C20 Directed graphs (digraphs), tournaments
Full Text: