Hamiltonian path

In the mathematical field of graph theory, a Hamiltonian path is a specific route through a network. This network is made of vertices, which are points, and edges, which are the lines connecting them. A Hamiltonian path is a sequence of edges that visits every single vertex in the graph exactly once. If this path is a cycle, meaning it ends at the same vertex where it began, it is called a Hamiltonian cycle or a Hamiltonian circuit.

A graph that contains such a path is known as a traceable graph. If a graph contains a Hamiltonian cycle, it is simply called a Hamiltonian graph.

There are several ways to define the relationships between these vertices and paths. A graph is considered Hamiltonian-connected if a Hamiltonian path exists between every possible pair of vertices. In some cases, a graph can undergo a Hamiltonian decomposition. This is an edge decomposition where the entire graph is split into several distinct Hamiltonian circuits. Some paths are also directed, meaning the edges act like one-way streets with arrows. In a directed graph, you must follow the direction from the tail of the arrow to its head.

Finding these paths is a major challenge in computer science. Determining whether a graph contains a Hamiltonian path or cycle is categorized as an NP-complete problem. This means it is a computationally difficult task for computers to solve as the graphs grow larger. Mathematicians use different tools to study these paths, such as the Hamiltonian cycle polynomial. This is an algebraic representation used for weighted digraphs. The polynomial is not zero if and only if the digraph is Hamiltonian.

The history of these ideas stretches back much further than the 19th century. In the 9th century, mathematicians in India named Rudrata and in the Islamic world named al-Adli ar-Rumi studied these concepts. They focused on the knight's tour, which is a Hamiltonian cycle on a chessboard's knight's graph. Later, in the 18th century, Abraham de Moivre and Leonhard Euler published work on these tours. William Rowan Hamilton, for whom these paths are named, invented the icosian game. This was a puzzle involving finding a Hamiltonian cycle on the edges of a dodecahedron.

Other researchers made important discoveries around the same time as Hamilton. Thomas Kirkman studied Hamiltonian cycles in polyhedra just one year before Hamilton did. Kirkman was notable for finding a polyhedron that did not have a Hamiltonian cycle. The Herschel graph is a famous example of this, as it is the smallest polyhedral graph without a Hamiltonian cycle.

While Hamilton used icosian calculus to solve his puzzle, that specific method does not work for all arbitrary graphs.

Mathematicians have developed theorems to predict when a graph will be Hamiltonian. In 1952, G. A. Dirac and Øystein Ore provided theorems stating that a graph is Hamiltonian if it has enough edges. In 1972, the Bondy-Chvátal theorem expanded on this by using the concept of a graph's closure. This process involves repeatedly adding edges between nonadjacent vertices until a specific property is met. If the resulting closure is a complete graph, the original graph is Hamiltonian.

Many different types of mathematical structures are Hamiltonian. For example, every platonic solid is considered a Hamiltonian graph. A complete graph with more than two vertices is always Hamiltonian. Every cycle graph is also Hamiltonian. Even certain complex structures, like the Cayley graph of a finite Coxeter group, have been found to be Hamiltonian. These patterns show how deeply these paths are embedded in the study of shapes and symmetry.