Non-Cayley vertex-transitive graphs and non-Cayley numbers

Graphs, Hypergraphs, and Computing

15 April 14:00 - 15:00

Cui Zhang - Technical University of Denmark, DTU

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.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to