TOPICS
Search

Hamiltonian Graph


HamiltonianGraphs

A Hamiltonian graph, also called a Hamilton graph, is a graph possessing a Hamiltonian cycle. A graph that is not Hamiltonian is said to be nonhamiltonian.

A Hamiltonian graph on n nodes has graph circumference n.

A graph possessing exactly one Hamiltonian cycle is known as a uniquely Hamiltonian graph.

While it would be easy to make a general definition of "Hamiltonian" that considers the singleton graph K_1 is to be either Hamiltonian or nonhamiltonian, defining "Hamiltonian" to mean "has a Hamiltonian cycle" and taking "Hamiltonian cycles" to be a subset of "cycles" in general would lead to the convention that the singleton graph is nonhamiltonian (B. McKay, pers. comm., Oct. 11, 2006). However, by convention, the singleton graph is generally considered to be Hamiltonian (B. McKay, pers. comm., Mar. 22, 2007). The convention in this work and in GraphData is that K_1 is Hamiltonian, while K_2=P_2 is nonhamiltonian.

The numbers of simple Hamiltonian graphs on n nodes for n=1, 2, ... are then given by 1, 0, 1, 3, 8, 48, 383, 6196, 177083, ... (OEIS A003216).

A graph can be tested to see if it is Hamiltonian in the Wolfram Language using HamiltonianGraphQ[g].

Testing whether a graph is Hamiltonian is an NP-complete problem (Skiena 1990, p. 196). Rubin (1974) describes an efficient search procedure that can find some or all Hamilton paths and circuits in a graph using deductions that greatly reduce backtracking and guesswork.

All Hamiltonian graphs are biconnected, although the converse is not true (Skiena 1990, p. 197). Any bipartite graph with unbalanced vertex parity is not Hamiltonian.

If the sums of the degrees of nonadjacent vertices in a graph G is greater than the number of nodes n for all subsets of nonadjacent vertices, then G is Hamiltonian (Ore 1960; Skiena 1990, p. 197).

All planar 4-connected graphs have Hamiltonian cycles, but not all polyhedral graphs do. For example, the smallest polyhedral graph that is not Hamiltonian is the Herschel graph on 11 nodes.

HamiltonianTetrahedron
HamiltonianOctahedron
HamiltonianCube
HamiltonianDodecahedron
HamiltonianIcosahedron
HamiltonianPlatonicCycles

All Platonic solids are Hamiltonian (Gardner 1957), as illustrated above.

HamiltonianArchimedean

Although not explicitly stated by Gardner (1957), all Archimedean solids have Hamiltonian circuits as well, several of which are illustrated above. However, the skeletons of the Archimedean duals (i.e., the Archimedean dual graphs are not necessarily Hamiltonian, as shown by Coxeter (1946) and Rosenthal (1946) for the rhombic dodecahedron (Gardner 1984, p. 98).

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


See also

Almost Hamiltonian Graph, Archimedean Dual Graph, Archimedean Graph, Barnette's Conjecture, Bicubic Graph, Chvátal's Theorem, Cyclic Graph, Eulerian Graph, Hamiltonian Cycle, Hamilton-Connected Graph, Hamiltonian Path, Hamiltonian Walk, Herschel Graph, Hypohamiltonian Graph, Hypotraceable Graph, Icosian Game, Longest Path, Meredith Graph, Nonhamiltonian Graph, Nonhamiltonian Vertex-Transitive Graph, Ore Graph, Tait's Hamiltonian Graph Conjecture, Traceable Graph, Traveling Salesman Problem, Tutte Conjecture, Uniquely Hamiltonian Graph

Explore with Wolfram|Alpha

References

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.Bollobás, B. Graph Theory: An Introductory Course. New York: Springer-Verlag, p. 12, 1979.Chartrand, G. Introductory Graph Theory. New York: Dover, p. 68, 1985.Chartrand, G.; Kapoor, S. F.; and Kronk, H. V. "The Many Facets of Hamiltonian Graphs." Math. Student 41, 327-336, 1973.Coxeter, H. S. M. "Problem E 711." Amer. Math. Monthly 53, 156, 1946.Dolch, J. P. "Names of Hamiltonian Graphs." In 4th S-E Conf. Combin., Graph Theory, Computing. Congress. Numer. 8, 259-271, 1973.Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150-156, May 1957.Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 96-97, 1984.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.Hamilton, W. R. Quart. J. Math., 5, 305, 1862.Hamilton, W. R. Philos. Mag. 17, 42, 1884.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 4, 1994.Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 219, 1973.Herschel, A. S. "Sir Wm. Hamilton's Icosian Game." Quart. J. Pure Applied Math. 5, 305, 1862.Lucas, E. Récréations mathématiques, Vol. 2. Paris: Gauthier-Villars, pp. 201 and 208-255, 1891.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.Ore, O. "A Note on Hamiltonian Circuits." Amer. Math. Monthly 67, 55, 1960.Rosenthal, A. "Solution to Problem E 711: Sir William Hamilton's Icosian Game." Amer. Math. Monthly 53, 593, 1946.Rubin, F. "A Search Procedure for Hamilton Paths and Circuits." J. ACM 21, 576-580, 1974.Skiena, S. "Hamiltonian Cycles." §5.3.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 196-198, 1990.Sloane, N. J. A. Sequence A003216/M2764 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Hamiltonian Graph

Cite this as:

Weisstein, Eric W. "Hamiltonian Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HamiltonianGraph.html

Subject classifications