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 has no Hamiltonian paths.

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

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

graph	formula
barbell graph
cocktail party graph
complete graph
complete bipartite graph
-crossed prism graph
cycle graph
gear graph
ladder graph
Möbius ladder
path graph	1
prism graph
sun graph
wheel graph

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

graph	order	recurrence
antiprism graph	9
crown graph	3
prism graph	6