[go: up one dir, main page]
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.

graphformula
barbell graph[(n-1)!]^2
cocktail party graph K_(n×2)(2n)!_1F_1(-n;-2n;-2)
complete graph K_nn!
complete bipartite graph K_(n,n)(n!)^2
2n-crossed prism graph6·2^(n-1)n(n+1)
cycle graph C_nn
gear graphn(n+1)
ladder graph P_2 square P_nn^2-n+2
Möbius ladder M_n1/2(-1)^nn[-1+(-1)^n(5+2n^2)]
path graph P_n1
prism graph Y_n1/2n[3+(-1)^n+2n^2]
sun graphn(n+1)
wheel graph W_n2(n-1)(n-2)

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