# Graphs, groups, and more: celebrating Brian Alspach’s 80th and Dragan Marušič’s 65th birthdays

from 28 May 2018 to 1 June 2018
Koper
UTC timezone
Home > Timetable > Contribution details

# Hamilton Paths and Cycles in Vertex-transitive Graphs

## Speakers

• Klavdija KUTNAR

## Content

A path (cycle) containing every vertex in a graph is called a Hamilton path (Hamilton cycle, respectively). A graph is called vertex-transitive if for any pair of vertices $u$ and $v$ there exists an automorphism mapping $u$ to $v$. In 1969, Lovasz asked whether every finite connected vertex-transitive graph has a Hamilton path. With the exception of the complete graph on two vertices, only four connected vertex-transitive graphs that do not have a Hamilton cycle are known to exist. These four graphs are the Petersen graph, the Coxeter graph and the two graphs obtained from them by replacing each vertex by a triangle. The fact that none of these four graphs is a Cayley graph has led to a folklore conjecture that every Cayley graph has a Hamilton cycle. (A Cayley graph is a graph whose automorphism group admits a regular subgroup.) Both of these two problems are still open. However, a considerable amount of partial results are known.

I will survey some results about the topic with special emphasis given to results obtained using methods initiated by Brian Alspach and/or Dragan Marušič.