Cui Zhang: Non-Cayley vertex-transitive graphs and non-Cayley numbers

A graph is vertex-transitive if its automorphism group acts transitively on its vertices. A graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. Thus, every Cayley graph is vertex- transitive. However, there are vertex-transitive graphs which are not Cayley graphs, the smallest example being the well-known Petersen graph. The order of a non-Cayley vertex-transitive graph is called a non-Cayley number.

In 1983, Dragan Marusic [D. Marusic, 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.

I will begin by introducing the research background and obtained outcomes on this topic and some of these connections. I will then explain one of methods on studying this topic by some examples.