TOPICS
Search

Nonhamiltonian Vertex-Transitive Graph


VertexTransitiveNonhamiltonian

There are exactly five known connected nonhamiltonian vertex-transitive graphs, namely the path graph P_2, the Petersen graph F_(010)A, the Coxeter graph F_(028)A, 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 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 2p except the Petersen graph is Hamiltonian. Marušič (1982) showed that every connected vertex-transitive graph of order p^2, p^3, 2p^2, and 3p is Hamiltonian, while Marušič and Parsons (1983) showed that connected vertex-transitive graphs of order 4p and 5p are traceable (Gould 1991).


See also

Cayley Graph, Hamilton Decomposition, Hamiltonian Graph, Lovász Conjecture, Middle Levels Conjecture, Middle Levels Graph, 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 5p." Disc. Math. 42, 227-242, 1982.Marušič, D. and Parsons, T. D. "Hamiltonian Paths in Vertex-Symmetric Graphs of Order 4p." 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.

Cite this as:

Weisstein, Eric W. "Nonhamiltonian Vertex-Transitive Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NonhamiltonianVertex-TransitiveGraph.html

Subject classifications