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