Importance: High ✭✭✭
Recomm. for undergrads: yes
Posted by: tchow
on: September 25th, 2008
Question   Is every Cayley graph Hamiltonian?

This problem seems to have been first considered by Rapaport-Strasser [R]. Lovasz [L] conjectured more generally that every vertex-transitive graph is Hamiltonian. For a survey of results up to 1996, see [CG]. Although many specific Cayley graphs have been shown to be Hamiltonian, there are few general results. One exception is the theorem by Pak and Radoičić [PR] that every finite group $ G $ with at least three elements has a generating set $ S $ of size $ |S| \le \log_2|G| $, such that the corresponding Cayley graph is Hamiltonian.


[CG] S. J. Curran, J. A. Gallian, Hamiltonian cycles and paths in Cayley graphs and digraphs—a survey, Discrete Math. 156 (1996), 1–18.

[L] L. Lovasz, Problem 11, in “Combinatorial structures and their applications,” University of Calgary, Calgary, Alberta, Canada (1970), Gordon and Breach, New York.

[PR] I. Pak and R. Radoičić, Hamiltonian paths in Cayley graphs, preprint.

*[R] E. Rapaport-Strasser, Cayley color groups and Hamilton lines, Scripta Math. 24 (1959), 51–58.

* indicates original appearance(s) of problem.


Comments are limited to a maximum of 1000 characters.
More information about formatting options