TOPICS
Search

Hamiltonian Cycle

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once (Skiena 1990, p. 196). A graph possessing a Hamiltonian cycle is said to be a Hamiltonian graph. By convention, the singleton graph K_1 is considered to be Hamiltonian even though it does not posses a Hamiltonian cycle, while the connected graph on two nodes K_2 is not.

The Hamiltonian cycle is named after Sir William Rowan Hamilton, who devised a puzzle in which such a path along the polyhedron edges of an dodecahedron was sought (the Icosian game).

A Hamiltonian cycle of a graph can be computed efficiently in the Wolfram Language using FindHamiltonianCycle[g][[All, All, 1]][[1]] (where the cycle returned is not necessarily the lexicographically first one). All simple (undirected) cycles of a graph can be computed time-efficiently (but with a memory overhead of more than 10 times that needed to represent the actual cycles) using Sort[FindHamiltonianCycle[g, All][[All, All, 1]]]. (Note the cycles returned are not necessarily returned in sorted order by default.) Possible Method options to FindHamiltonianCycle include "Backtrack", "Heuristic", "AngluinValiant", "Martello", and "MultiPath". In addition, the Wolfram Language command FindShortestTour[g] attempts to find a shortest tour, which is a Hamiltonian cycle (with initial vertex repeated at the end) for a Hamiltonian graph G if it returns a list with first element equal to the vertex count of G.

Precomputed lists of Hamiltonian cycles for many named graphs can be obtained using GraphData[graph, "HamiltonianCycles"]. Precomputed counts of the corresponding number of Hamiltonian cycles may similarly be obtained using GraphData[graph, "HamiltonianCycleCount"]..

The total numbers of directed Hamiltonian cycles for all simple graphs of orders n=1, 2, ... are 0, 0, 2, 10, 58, 616, 9932, 333386, 25153932, 4548577688, ... (OEIS A124964).

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

In general, the problem of finding a Hamiltonian cycle is NP-complete (Karp 1972; Garey and Johnson 1983, p. 199), so the only known way to determine whether a given general graph has a Hamiltonian cycle is to undertake an exhaustive search. 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. A probabilistic algorithm due to Angluin and Valiant (1979), described by Wilf (1994), can also be useful to find Hamiltonian cycles and paths.

HamiltonianTetrahedronHamiltonianOctahedronHamiltonianCubeHamiltonianDodecahedronHamiltonianIcosahedron
HamiltonianPlatonicCycles

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

Khomenko and Golovko (1972) gave a formula giving the number of graph cycles of any length, but its computation requires computing and performing matrix operations involving all subsets up to size n-2, making it computationally expensive. A greatly simplified and improved version of the Khomenko and Golovko formula for the special case of n-cycles (i.e., Hamiltonian cycles) gives

c_n=1/(2n)sum_(i=2)^n(-1)^(n-i)sum_(|S|=n-i)Tr(A_S^n),

where A_S^k is the kth matrix power of the submatrix of the adjacency matrix A with the subset S of rows and columns deleted (Perepechko and Voropaev).

The following table summarizes the numbers of (undirected) Hamiltonian cycles on various classes of graphs. The n-hypercube is considered by Gardner (1986, pp. 23-24), who however gives the counts for an n-hypercube for n=1, 2, ... as 2, 8, 96, 43008, ... (OEIS A006069) which must be divided by 2^n to get the number of distinct (directed) cycles counting shifts of points as equivalent regardless of starting vertex.

graphOEISsequence
Andrásfai graphA3079020, 1, 5, 145, 8697, 1109389, 236702901, ...
antiprism graphA306447X, X, 16, 29, 56, 110, 225, 469, 991, 2110, 4511, ...
(n,n)-black bishop graphA307920X, X, 0, 4, 704, 553008, , 13802629632, 1782158930138112, ...
cocktail party graph K_(n×2)A3079230, 1, 16, 744, 56256, ...
complete graph K_nA0017100, 0, 1, 3, 12, 60, 360, 2520, 20160, 181440, ...
complete bipartite graph K_(n,n)A0107960, 1, 6, 72, 1440, 43200, 1814400, ...
complete tripartite graph K_(n,n,n)A3079241, 16, 1584, 463104, 29928960, ...
2n-crossed prism graphA007283X, X, X, 6, 12, 24, 48, 96, 192, 384, 768, 1536, ...
crown graphA3064961, 6, 156, 4800, 208440, 11939760, 874681920, ...
cube-connected cycle graphA000000X, X, 6, 28628, ...
cycle graph C_nA000012X, X, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
folded cube graphA307925X, 0, 3, 72, 23760, 332012113920, ...
grid graph P_n square P_nA0037630, 1, 0, 6, 0, 1072, 0, 4638576, 0, ...
grid graph P_n square P_n square P_nA0000000, 6, 0, ?, 0, ...
halved cube graphA3079260, 0, 3, 744, 986959440, 312829871511322359060480, ...
hypercube graph Q_nA0660370, 1, 6, 1344, 906545760, ...
(n,n)-king graphA140519X, 3, 16, 2830, 2462064, 22853860116, ...
(n,n)-knight graphA001230X, 0, 0, 0, 0, 9862, 0, 13267364410532, ...
n-ladder graphA0574270, 1, 1, 1, 1, 1, 1, ...
Möbius ladderA103889X, X, X, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, 16, 15, ...
Mycielski graphA3079270, 1, 10, 102310, ...
odd graphA301557X, 1, 0, 1419264, ...
permutation star graphA0000000, 0, 1, 18, ...
prism graph Y_nA103889X, X, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, 16, ...
(n,n)-queen graphA3079280, 3, 1960, 402364270, 39741746126749664, ...
rook graph K_n square K_nA269561X, 1, 48, 284112, 167875338240, ...
sun graphA000012X, X, 1, 1, 1, 1, 1, 1, ...
torus grid graph C_n square C_nA222199X, X, 48, 1344, 23580, 3273360, ...
transposition graphA3078960, 0, 6, 569868288, ...
triangular graphA307930X, 0, 1, 16, 3216, 9748992, ...
triangular grid graphA1126761, 1, 3, 26, 474, 17214, 685727, ...
wheel graph W_nA000027X, X, X, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
(n,n)-white bishop graphA307929X, X, 1, 4, 396, 553008, 4701600128, 1782158930138112, ...

Closed forms for some of these classes of graphs are summarized in the following table, where alpha, beta, and gamma are the roots of x^3-x^2-2x-1 and K_x(x) is a modified Bessel function of the second kind.

graphformula
antiprism graph(2n+alpha^n+beta^n+gamma^n)
cocktail party graph K_(n×2)1/2(2n-1)!_1F_1(-n,1-2n;-2)
complete graph K_n1/2(n-1)!
complete bipartite graph K_(n,n)1/2n!(n-1)!
complete tripartite graph K_(n,n,n)2^(n-1)(n-1)!(n!)2_3F_2(1/2(n-1),-1/2n,n;1,1,1)
2n-crossed prism graph3/2·2^n
crown graph(-1)^n(n-1)!+n!sum_(j=0)^(n-1)(-1)^j(n-j-1)!(2n-j-1; j)
=1/2(n-1)!nint(2ne^(-2)K_n(2))
cycle graph C_n1
Hanoi graph1
ladder graph P_2 square P_n1
Möbius ladder M_n2+n-(-1)^n
prism graph Y_n(-1)^n+n+1
sun graph1
wheel graph W_nn-1

See also

Chvátal's Theorem, Dirac's Theorem, Eulerian Cycle, Euler Graph, Grinberg Formula, Hamiltonian Graph, Hamiltonian Path, Hamiltonian Walk, Herschel Graph, Icosian Game, Kozyrev-Grinberg Theory, Longest Path, Middle Levels Conjecture, Ore's Theorem, Pósa's Theorem, Smith's Network Theorem, Tour, Traveling Salesman Problem, Unicursal Circuit, Uniquely Hamiltonian Graph

Explore with Wolfram|Alpha

References

Angluin, D. and Valiant, L. "Probabilistic Algorithms for Hamiltonian Circuits and Matchings." J. Comput. Sys. Sci. 18, 155-190, 1979.Bollobás, B. Graph Theory: An Introductory Course. New York: Springer-Verlag, p. 12, 1979.Chalaturnyk, A. "A Fast Algorithm for Finding Hamilton Cycles." Master's thesis. Winnipeg, Manitoba, Canada: University of Manitoba, 2008. ftp://www.combinatorialmath.ca/g&g/chalaturnykthesis.pdf.Chartrand, G. Introductory Graph Theory. New York: Dover, p. 68, 1985.Csehi, C. Gy. and Tóth, J. "Search for Hamiltonian Cycles." Mathematica J. 13, 2011. http://www.mathematica-journal.com/2011/05/search-for-hamiltonian-cycles/.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.Gardner, M. "The Binary Gray Code." In Knotted Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman, pp. 23-24, 1986.Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1983.Karp, R. M. "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations (Ed. R. E. Miller and J. W. Thatcher). New York: Plenum Press, pp. 85-103, 1972.Khomenko, N. P. and Golovko, L. D. "Identifying Certain Types of Parts of a Graph and Computing Their Number." Ukr. Math. J. 24, 313-321, 1972.Kocay, W. "An Extension of the Multi-Path Algorithm for Hamilton Cycles." Disc. Math. 101, 171-188, 1992.Kocay, W. and Li, B. "An Algorithm for Finding a Long Path in a Graph." Util. Math. 45, 169-185, 1994.Lederberg, J. "Hamilton Circuits of Convex Trivalent Polyhedra (up to 18 Vertices)." Amer. Math. Monthly 74, 522-527, 1967.Ore, O. "A Note on Hamiltonian Circuits." Amer. Math. Monthly 67, 55, 1960.Perepechko, S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."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. Sequences A003042/M2053, A005843/M0985, A006069/M1903, A007395/M0208, A094047, A124349, A124355, A124356, A129348, A129349, A143246, A143247, A143248, A174589, A222199, A280847, A281255, A301557, A306447, A307896, A307902in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. "On Hamiltonian Circuits." J. London Math. Soc. 21, 98-101, 1946.Vandegriend, "B. Finding Hamiltonian Cycles: Algorithms, Graphs and Performance." Master's thesis, Winnipeg, Manitoba, Canada: University of Manitoba, 1998.Wilf, H. S. Algorithms and Complexity. pp. 120-122. Summer, 1994. http://www.math.upenn.edu/~wilf/AlgoComp.pdf.

Referenced on Wolfram|Alpha

Hamiltonian Cycle

Cite this as:

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

Subject classifications