Seminar

# 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.

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.

Organizers

Magnus M. Halldorsson

Reykjavik University

Klas Markström

Umeå University

Andrzej Rucinski

Adam Mickiewicz University

Carsten Thomassen

Technical University of Denmark, DTU