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
Adam Mickiewicz University
Technical University of Denmark, DTU