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.


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: EuDML EMIS