TOPICS
Search

Hamiltonian Path


A Hamiltonian path, also called a Hamilton path, is a graph path between two vertices of a graph that visits each vertex exactly once. If a Hamiltonian path exists whose endpoints are adjacent, then the resulting graph cycle is called a Hamiltonian cycle (or Hamiltonian cycle).

A graph that possesses a Hamiltonian path is called a traceable graph.

In general, the problem of finding a Hamiltonian path is NP-complete (Garey and Johnson 1983, pp. 199-200), so the only known way to determine whether a given general graph has a Hamiltonian path is to undertake an exhaustive search

Any bipartite graph with a vertex parity unbalance >1 has no Hamiltonian paths.

Finding a single Hamiltonian path of a graph g is implemented in the Wolfram Language as FindHamiltonianPath[g]. All Hamiltonian paths of a given graph can be found (inefficiently) using the command HamiltonianPath[g, All] in the Wolfram Language package Combinatorica` . A precomputed list of all Hamiltonian paths for many named graphs can be obtained using GraphData[graph, "HamiltonianPaths"], where and both orientations of paths are included (so that {1, 2, 3} is considered distinct from {3, 2, 1}). A precomputed count of the corresponding number of Hamiltonian paths is given by GraphData[graph, "HamiltonianPathCount"].

The total numbers of directed Hamiltonian paths for all simple graphs of orders n=1, 2, ... are 0, 2, 8, 50, 416, 5616, 117308, 4862736, ... (OEIS A193352).

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. A Hamiltonian path between two vertices i and j can be found if an algorithm for Hamiltonian cycles is available. This can be done by checking if the original graph G contains the edge (i,j) and adding it if not to obtain G^'. Since a Hamiltonian path with adjacent endpoints is a Hamiltonian cycle and since i and j are now adjacent, finding a Hamiltonian cycle and splitting at the edge gives a Hamiltonian path from i to j in G. Similarly, if no Hamiltonian cycle exists in G^', then there is no Hamiltonian path from i to j in G.

The Lovász conjecture states that without exception, every connected vertex-transitive graph is traceable.

The following table summarizes the numbers of (undirected) Hamiltonian paths on various classes of graphs.

Recurrence relations for the number of directed Hamiltonian paths for some graph families are summarized below.

graphorderrecurrence
antiprism graph9a_n=a_(n-9)+a_(n-8)-3a_(n-7)-5a_(n-6)+5a_(n-5)+7a_(n-4)-4a_(n-3)-6a_(n-2)+5a_(n-1)
crown graph3a_n=n(n-1)^2a_(n-2)+(n-2)n(n-1)a_(n-3)+n(n-1)a_(n-1)
prism graph Y_n6a_n=-a_(n-6)+2a_(n-5)+a_(n-4)-4a_(n-3)+a_(n-2)+2a_(n-1)

See also

Graph Cycle, Graph Path, Hamiltonian Cycle, Hamiltonian Graph, Hamiltonian Walk, Longest Path, Lovász Conjecture, Tournament, Traceable 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.Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, p. 199, 1983.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.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.Rubin, F. "A Search Procedure for Hamilton Paths and Circuits." J. ACM 21, 576-580, 1974.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 175, 1990.Sloane, N. J. A. Sequences A005843, A006070/M5295, A046092, A158664, A033996, A091299, A096969, A096970, A124350, A124352, A137890, A137892, A165134, A193346, and A233826 in "The On-Line Encyclopedia of Integer Sequences."Wilf, H. S. Algorithms and Complexity. pp. 120-122. Summer, 1994. http://www.math.upenn.edu/~wilf/AlgoComp.pdf.

Referenced on Wolfram|Alpha

Hamiltonian Path

Cite this as:

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

Subject classifications