There are exactly five known connected nonhamiltonian vertex-transitive graphs, namely the path
graph 
, 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.
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 layer graphs are Hamitlonian, 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).
See also
Cayley Graph, Hamilton Decomposition, Hamiltonian Graph, Lovász Conjecture, Middle Layer Graph, Middle Levels Conjecture, Nonhamiltonian Graph, Triangle-Replaced Graph, Vertex-Transitive Graph
Explore with Wolfram|Alpha
References
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.
Referenced on Wolfram|Alpha
Nonhamiltonian Vertex-Transitive Graph
Cite this as:
Weisstein, Eric W. "Nonhamiltonian Vertex-Transitive Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/NonhamiltonianVertex-TransitiveGraph.html