The Hamiltonian number h(n) of a connected graph G is the length of a Hamiltonian walk G. In other words, it is the minimum length of a closed spanning walk in the graph. For a Hamiltonian graph, h(G) = left bracketing bar G right bracketing bar , where left bracketing bar G right bracketing bar is the vertex count. The Hamiltonian number therefore gives one measure of how far away a graph is from being Hamiltonian, and a graph with h(G) = n + 1 is called an almost Hamiltonian graph.

almost Hamiltonian graph | graph circumference | Hamiltonian graph | Hamiltonian walk