Hamiltonian Graphs

Understanding Hamiltonian Graphs

• A Hamiltonian graph is a type of graph that possesses a Hamiltonian cycle, a closed loop that visits each vertex in the graph exactly once.
• A Hamiltonian path is similar to a Hamiltonian cycle but it does not need to return to the starting vertex.
• It is named after the Irish mathematician Sir William Rowan Hamilton who studied paths and cycles in such graphs.

Properties of Hamiltonian Graphs

• There is no general formula to determine whether a graph is Hamiltonian or not, as this problem is known to be NP-complete.
• The concept of the Hamiltonian graph plays a significant role in various fields of studies such as in computer science, information routing, and network topology.
• A complete graph with more than two vertices is always Hamiltonian as it possesses a Hamiltonian cycle.
• If a graph has a vertex of degree one, it cannot be Hamiltonian, since a cycle would require at least two edges incident to each vertex.

Dirac’s and Ore’s Theorems on Hamiltonian Graph

• Dirac’s theorem states a sufficient condition for a graph to be Hamiltonian: if every vertex in the graph has a degree half the total number of vertices or more, the graph is Hamiltonian.
• Ore’s theorem is an extension of Dirac’s theorem: if the sum of the degrees of any two non-adjacent vertices is greater than or equal to the total number of vertices in the graph, then the graph is Hamiltonian.

Hamiltonian Circuits and the Traveling Salesman Problem

• The Hamiltonian cycle problem is famously related to the Traveling Salesman Problem (TSP), an optimization problem trying to determine the shortest possible route for a salesman who needs to visit a set of cities and return to the starting point.
• While it may seem simple to state, both the Hamiltonian cycle problem and the Traveling Salesman Problem have been proven to be NP-hard, meaning no efficient solution exists that is guaranteed to be correct for all cases.