TOPICS
Search

Nonhamiltonian Vertex-Transitive Graph

VertexTransitiveNonhamiltonian

Lovász (1970) conjectured that every connected vertex-transitive graph is traceable (Gould, p. 33). This conjecture was subsequently verified for several special orders and classes. Furthermore, with a few notable exceptions, such graphs were also shown to be Hamiltonian. Babai proved the conjecture for graphs with prime order p>2 (Bondy and Murty 1976, Lipman 1985, Gould).

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, p. 33).

Thomassen (1991) conjectured that there are only a finite number of connected nonhamiltonian vertex-transitive graphs, while Babai (1979, 1996) conjectured that there are infinitely many.

There are currently only five known connected nonhamiltonian vertex-transitive graphs, namely the path graph K_2, the Petersen graph F_(10)A, the Coxeter graph F_(28)A, and the triangle-replaced Petersen and Coxeter graphs (the first of these being the cubic vertex-transitive graph Ct66). It is conjectured that all other connected vertex-transitive graphs are Hamiltonian (Godsil and Royle 2001, p. 45).

A slightly weaker conjecture is that all Cayley graphs are Hamiltonian (Royle). Conversely, all Cayley graphs are vertex-transitive.

See also

Cayley Graph, Hamilton Decomposition, Hamiltonian 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, 2 vols. (Ed. R. L. Graham, M. Grötschel, M.; and L. Lovász). Cambridge, MA: MIT Press, pp. 1447-1540, 1996.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." n.d. http://www.mathcs.emory.edu/~rg/updating.pdf.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.Lovász, L. Problem 11 in "Combinatorial Structures and Their Applications." In Proc. Calgary Internat. Conf. Calgary, Alberta, 1969. London: Gordon and Breach, pp. 243-246, 1970.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.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