Nonhamiltonian Vertex-Transitive Graph

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  (Bondy and Murty 1976, Lipman 1985, Gould).

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, 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 , the Petersen graph , the Coxeter graph , 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.

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 ." 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.

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.