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

Gvozdjak, P.; Širáň, J.

Acta Math. Univ. Comen., New Ser. 63, No. 2, 309-313 (1994).

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.

Reviewer: M.E.Watkins (Syracuse)

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

Keywords:

non-Cayley graphs; map; 2-manifold; orientably regular; closed walk; Cayley graph; regular subgroup; arc-transitive