A nonhamiltonian graph is a graph that is not Hamiltonian. All disconnected graphs are therefore nonhamiltoinian, as are acylic graphs.
Classes of connected graphs that are nonhamiltonian include barbell graphs, gear graphs, helm graphs, hypohamiltonian graphs, kayak paddle graphs, lollipop graphs, Menger sponge graphs, pan graphs, nontrivial path graphs, snarks, star graphs, sun graphs, sunlet graphs, tadpole graphs, nontrivial trees , weak snarks, web graphs, and windmill graphs.
A graph can be determined to be nonhamiltonian in the Wolfram Language using HamiltonianGraphQ[g] and precomputed values are available for a number of named graphs using GraphData[graph, "Nonhamiltonian"].
The numbers of connected simple nonhamiltonian graphs on , 2, ... nodes are 0, 1, 1, 3, 13, 64, 470, 4921, ... (OEIS A126149), the first few of which are illustrated above, and the corresponding number of not-necessarily-connected simple nonhamiltonian graphs on , 2, ... nodes are 0, 2, 3, 8, 26, 108, 661, 6150, 97585, ... (OEIS A246446).
There are no nonhamiltonian polyhedral graphs on 10 and fewer nodes, and the numbers for , 12, ... are 74, 1600, 43984, 1032208, 22960220, ... (OEIS A007033). The most notable of 11-node graphs are the Herschel graph and Goldner-Harary graph.
The following table summarizes some small named connected nonhamiltonian graphs.
graph | |
singleton graph | 1 |
claw graph | 4 |
theta-0 graph | 7 |
Petersen graph | 10 |
Herschel graph | 11 |
no perfect matching graph | 16 |
first Blanuša snark | 18 |
second Blanuša snark | 18 |
flower snark | 20 |
Coxeter graph | 28 |
double star snark | 30 |
Thomassen graph | 34 |
Tutte's graph | 46 |
Szekeres snark | 50 |
Meredith graph | 70 |