Hamiltonian path
Hamiltonian paths and cycles are named after William Rowan Hamilton, who invented the icosian game, now also known as Hamilton's puzzle, which involves finding a Hamiltonian cycle in the edge graph of the dodecahedron.
[1] Even earlier, Hamiltonian cycles and paths in the knight's graph of the chessboard, the knight's tour, had been studied in the 9th century in Indian mathematics by Rudrata, and around the same time in Islamic mathematics by al-Adli ar-Rumi.
In 18th century Europe, knight's tours were published by Abraham de Moivre and Leonhard Euler.
Similar notions may be defined for directed graphs, where each edge (arc) of a path or cycle can only be traced in a single direction (i.e., the vertices are connected with arrows and the edges traced "tail-to-head").
A Hamilton maze is a type of logic puzzle in which the goal is to find the unique Hamiltonian cycle in a given graph.
The best vertex degree characterization of Hamiltonian graphs was provided in 1972 by the Bondy–Chvátal theorem, which generalizes earlier results by G. A. Dirac (1952) and Øystein Ore.
[11] Dirac and Ore's theorems basically state that a graph is Hamiltonian if it has enough edges.
The Bondy–Chvátal theorem operates on the closure cl(G) of a graph G with n vertices, obtained by repeatedly adding a new edge uv connecting a nonadjacent pair of vertices u and v with deg(v) + deg(u) ≥ n until no more pairs with this property can be found.
) is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is n or greater.
The following theorems can be regarded as directed versions: Ghouila–Houiri (1960) — A strongly connected simple directed graph with n vertices is Hamiltonian if every vertex has a full degree greater than or equal to n. Meyniel (1973) — A strongly connected simple directed graph with n vertices is Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to
Many of these results have analogues for balanced bipartite graphs, in which the vertex degrees are compared to the number of vertices on a single side of the bipartition rather than the number of vertices in the whole graph.
