Time

Oct 22 2008 - 3:30pm - 4:18 pm

Location

MW 154

Speaker

Klavdija Kutnar (University of Primorska and O.S.U.)

Abstract

A path (cycle) containing every vertex in a graph is called a Hamilton path (Hamilton cycle).  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 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 contains a regular subgroup.)  Both of these two problems are still open.  However, a considerable number of partial results are known.  In this talk, a special emphasis will be given to recent results concerning the existence of Hamilton cycles in cubic Cayley graphs arising from groups having a (2,s,3)-presentation.