Hamiltonian Graph

A Hamiltonian graph, also called a Hamilton graph, is a graph possessing a Hamiltonian cycle. A graph that is not Hamiltonian is said to be nonhamiltonian.

A Hamiltonian graph on nodes has graph circumference .

While it would be easy to make a general definition of "Hamiltonian" that goes either way as far as the singleton graph is concerned, defining "Hamiltonian" to mean "has a Hamiltonian cycle" and taking "Hamiltonian cycles" to be a subset of "cycles" in general would lead to the convention that the singleton graph is nonhamiltonian (B. McKay, pers. comm., Oct. 11, 2006). However, by convention, the singleton graph is generally considered to be Hamiltonian (B. McKay, pers. comm., Mar. 22, 2007). The convention in this work and in GraphData is that is Hamiltonian, while is nonhamiltonian.

The numbers of simple Hamiltonian graphs on nodes for , 2, ... are then given by 1, 0, 1, 3, 8, 48, 383, 6196, 177083, ... (OEIS A003216).

A graph can be tested to see if it is Hamiltonian in the Wolfram Language using HamiltonianGraphQ[g].

Testing whether a graph is Hamiltonian is an NP-complete problem (Skiena 1990, p. 196). Rubin (1974) describes an efficient search procedure that can find some or all Hamilton paths and circuits in a graph using deductions that greatly reduce backtracking and guesswork.

All Hamiltonian graphs are biconnected, although the converse is not true (Skiena 1990, p. 197). Any bipartite graph with unbalanced vertex parity is not Hamiltonian.

If the sums of the degrees of nonadjacent vertices in a graph is greater than the number of nodes for all subsets of nonadjacent vertices, then is Hamiltonian (Ore 1960; Skiena 1990, p. 197).

All planar 4-connected graphs have Hamiltonian cycles, but not all polyhedral graphs do. For example, the smallest polyhedral graph that is not Hamiltonian is the Herschel graph on 11 nodes.

All Platonic solids are Hamiltonian (Gardner 1957), as illustrated above.

Although not explicitly stated by Gardner (1957), all Archimedean solids have Hamiltonian circuits as well, several of which are illustrated above. However, the skeletons of the Archimedean duals (i.e., the Archimedean dual graphs are not necessarily Hamiltonian, as shown by Coxeter (1946) and Rosenthal (1946) for the rhombic dodecahedron (Gardner 1984, p. 98).

Wolfram Web Resources