TOPICS

# Nonhamiltonian Graph

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

Bicubic Nonhamiltonian Graph, Cubic Nonhamiltonian Graph, Hamiltonian Graph, Horton Graphs, Maximally Nonhamiltonian Graph, Nonhamiltonian Vertex-Transitive Graph, Quartic Nonhamiltonian Graph, Quintic Nonhamiltonian Graph, Snark, Tait's Hamiltonian Graph Conjecture, Tutte Conjecture, Tutte's Graph, Untraceable Graph, Vertex-Transitive Graph, Weak Snark

## Explore with Wolfram|Alpha

More things to try:

## References

Aldred, R. E. L.; Bau, S.; Holton, D. A.; and McKay, B. D. "Nonhamiltonian 3-Connected Cubic Planar Graphs." SIAM J. Disc. Math. 13, 25-32, 2000.Royle, G. "Cubic Symmetric Graphs (The Foster Census): Hamiltonian Cycles." http://school.maths.uwa.edu.au/~gordon/remote/foster/#hamilton.Sloane, N. J. A. Sequences A007033/M5351, A126149, and A246446 in "The On-Line Encyclopedia of Integer Sequences."

## Referenced on Wolfram|Alpha

Nonhamiltonian Graph

## Cite this as:

Weisstein, Eric W. "Nonhamiltonian Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NonhamiltonianGraph.html