On cubic non-Cayley vertex-transitive graphs

✍ Scribed by Klavdija Kutnar,; Dragan Marušič;; Cui Zhang

• Publisher: John Wiley and Sons
• Year: 2011
• Tongue: English
• Weight: 197 KB
• Volume: 69
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20573

✦ Synopsis

Abstract

In 1983, the second author [D. Marušič, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non‐Cayley vertex‐transitive graph on n vertices. (The term non‐Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ϑ(n) among valencies of non‐Cayley vertex‐transitive graphs of order n. As cycles are clearly Cayley graphs, ϑ(n)⩾3 for any non‐Cayley number n.

In this paper a goal is set to determine those non‐Cayley numbers n for which ϑ(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non‐Cayley vertex‐transitive graphs of order n. It is known that for a prime p every vertex‐transitive graph of order p, p^2^ or p^3^ is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non‐Cayley vertex‐transitive graph of order 2__p__, 4__p__ or 2__p__^2^ is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non‐Cayley vertex‐transitive graph of order 4__p__^2^, p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2__p__^k^, where p>7 is a prime and k⩽p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012