Abstract: Klavdija Kutnar

CONSTRUCTION OF HAMILTON CICLES IN (2,s,3)-CAYLEY GRAPHS

            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. 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 (2,s,3)-presentation.