Klavdija Kutnar
University of Primorska, Koper, Slovenia

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. Special emphasis will be given to a solution to one of the problems posted recently by Gregor, Merino and Mütze, together with a connection to another long standing problem regarding vertex-transitive graphs - the problem about the existence of semiregular automorphisms in vertex-transitive graphs.