Hamiltonicity in Cayley graphs and digraphs

Abstract

The existence of Hamiltonian paths and cycles has always been of interest, not necessarily just within graph theory. For example, the problem bears a strong relation with group theory: given a finite set of generators of a group, can one construct a finite sequence s1,s2, . . .sr from these generators such that every word s1s2 . . .si corresponds to a unique element of the group? Such a sequence of words would imply a Hamiltonian path in the Cayley graph of the group with the given generators forming the connecting set. We begin by introducing fundamental elements of graph and group theory, and the notion of a Cayley graph. We then introduce a conjecture of Lovász, on the existence of Hamiltonian cycles in finite connected Cayley graphs. In this manner we reconcile the Hamiltonian problem in graph and group theory. We then introduce a number of techniques, through which a number of classes of groups have been shown to have Hamiltonian Cayley graphs. We use these techniques to prove a result of Marušiˇc (1983), that every Cayley graph for every finite Abelian group has a Hamiltonian cycle. We will also consider the pioneering work of Rankin (1948, 1966) on groups with a generating set of size 2. We also consider Cayley digraphs and provide examples of infinite classes of such graphs which do not have a Hamiltonian cycle. Consequently, a variant of Lovász’s conjecture for Cayley digraphs cannot be stated. However, we prove a result of Holszty ´nski and Strube (1978) that every Cayley digraph of an Abelian group has a Hamiltonian path, hence providing a holistic overview of the problem in the case of Abelian groups. We conclude by proving a modern result, due to Pak and Radoici´c ˘ (2009), showing that every group has a small generating set such that the corresponding Cayley graph has a Hamiltonian cycle. This is followed by a short survey of further results and open problems. In this manner, we hope to present the reader with a foundation for carrying out research in this area, along with evidence suggesting that Lovász’s conjecture for Cayley graphs holds in the positive.