Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

A path (cycle) containing every vertex in a graph is called a Hamilton path (Hamilton cycle, respectively). Hamilton cycles have been studied extensively in graph theory for their own sake, because of connections with the four color problem, and the travelling salesman problem. 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, thus tying together two seemingly unrelated concepts: traversability and symmetry of graphs. 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 an overview of these results will be introduced. 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.