Establishing or refuting Thomassen's conjecture remains an difficult open problem, as attested to by the fact that the middle
levels conjecture, which posited that middle
level graphs are HamitlonianHamiltonian Graph,
was proven only relatively recently ((Mütze 2016, Mütze 2024).
A slightly weaker conjecture is that all Cayley graphs are Hamiltonian (Royle). Conversely, all Cayley graphs
are vertex-transitive.
Alspach (1979) showed that every connected vertex-transitive graph of order except the Petersen graph
is Hamiltonian. Marušič (1982) showed
that every connected vertex-transitive graph of order , , , and is Hamiltonian, while
Marušič and Parsons (1983) showed that connected vertex-transitive graphs
of order and are traceable (Gould 1991).
Babai, L. Problem 17 in "Unsolved Problems." In Summer Research Workshop in Algebraic Combinatorics. Simon Fraser University,
Jul. 1979.Babai, L. "Automorphism Groups, Isomorphism, Reconstruction."
Ch. 27 in Handbook
of Combinatorics, Vol. 2 (Ed. R. L. Graham, M. Grötschel,
M.; and L. Lovász). Cambridge, MA: MIT Press, pp. 1447-1540, 1996.Bermond,
J.-C. "Hamiltonian Graphs." Ch. 6 in Selected
Topics in Graph Theory (Ed. L. W. Beineke and R. J. Wilson).
London: Academic Press, pp. 127-167, 1979.Bondy, J. A. and
Murty, U. S. R. Graph
Theory with Applications. New York: North Holland, 1976.Bryant,
D. and Dean, M. "Vertex-Transitive Graphs that have no Hamilton Decomposition."
25 Aug 2014. http://arxiv.org/abs/1408.5211.Godsil,
C. and Royle, G. "Hamilton Paths and Cycles." C§3.6 in Algebraic
Graph Theory. New York: Springer-Verlag, pp. 45-47, 2001.Gould,
R. J. "Updating the Hamiltonian Problem--A Survey." J. Graph Th.15,
121-157, 1991.Kutnar, K. and Marušič, D. "Hamilton
Cycles and Paths in Vertex-Transitive Graphs-Current Directions." Disc. Math.309,
5491-5500, 2009.Lipman, M. "Hamiltonian Cycles and Paths in Vertex-Transitive
Graphs with Abelian and Nilpotent Groups." Disc. Math.54, 15-21,
1985.Marušič, D. "Hamiltonian Paths in Vertex-Symmetric
Graphs of Order ." Disc. Math.42, 227-242, 1982.Marušič,
D. and Parsons, T. D. "Hamiltonian Paths in Vertex-Symmetric Graphs of
Order ." Disc. Math.43, 91-96, 1983.Mütze,
T. "Proof of the Middle Levels Conjecture." Proc. Lond. Math. Soc.112,
677-713, 2016.Mütze, T. "On Hamilton Cycles in Graphs Defined
by Intersecting Set Systems." Not. Amer. Soc.74, 583-592, 2024.Royle,
G. "Transitive Graphs." http://school.maths.uwa.edu.au/~gordon/trans/.Thomassen,
C. "Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on
a Fixed Surface." Trans. Amer. Math. Soc.323 605-635, 1991.
, the Petersen graph 
,
the Coxeter graph 
, the triangle-replaced Petersen, and the triangle-replaced Coxeter graph. As attributed by Gould (1991) citing
Bermond (1979), Thomassen conjectured that all other connected vertex-transitive graphs are Hamiltonian
(cf. Godsil and Royle 2001, p. 45; Mütze 2024). In contrast, Babai (1979,
1996) conjectured that there are infinitely many connected vertex-transitive graphs
that are nonhamiltonian.
except the Petersen graph
is Hamiltonian. Marušič (1982) showed
that every connected vertex-transitive graph of order 
, 
, 
, and 
is Hamiltonian, while
Marušič and Parsons (1983) showed that connected vertex-transitive graphs
of order 
and 
are traceable (Gould 1991).
." Disc. Math. 42, 227-242, 1982.Marušič,
D. and Parsons, T. D. "Hamiltonian Paths in Vertex-Symmetric Graphs of
Order 
." Disc. Math. 43, 91-96, 1983.Mütze,
T. "Proof of the Middle Levels Conjecture." Proc. Lond. Math. Soc. 112,
677-713, 2016.Mütze, T. "On Hamilton Cycles in Graphs Defined
by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.Royle,
G. "Transitive Graphs."