Home > Timetable > Contribution details

Contribution

Hamilton Paths and Cycles in Vertex-transitive Graphs

Speakers

  • Klavdija KUTNAR

Primary authors

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