TOPICS
Search

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"].

NonhamiltonianGraphs

The numbers of connected simple nonhamiltonian graphs on n=1, 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 n=1, 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 n=11, 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.


See also

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

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

Subject classifications