A Hamiltonian walk on a connected graph is a closed walk of minimal length which visits every vertex of a graph (and may visit vertices and edges multiple times). For example, a Hamiltonian walk on the above 3-pan graph is given by the vertex sequence 4, 3, 1, 2, 3, 4 and hence is of length 5. The length of a Hamiltonian walk in a graph G is called the Hamiltonian number h(G). A Hamiltonian graph has h(G) = n, where n = left bracketing bar G right bracketing bar is the vertex count. A graph with h(G) = n + 1 is said to be almost Hamiltonian.

almost Hamiltonian graph | Hamiltonian cycle | Hamiltonian graph | k-cyclic graph | walk