TOPICS
Search

Nonhamiltonian Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A nonhamiltonian graph is a graph that is not Hamiltonian. All disconnected graphs are therefore nonhamiltonian, as are acyclic graphs with at least two vertices. The singleton graph is treated as Hamiltonian here, consistent with the counts below and the Wolfram Language convention.

A bipartite graph with at least two vertices and bipartition classes of unequal sizes is nonhamiltonian, since any Hamiltonian cycle in a bipartite graph would have to alternate between the two bipartition classes and therefore use equally many vertices from each. Equal bipartition sizes are not sufficient for Hamiltonicity in general. For example, the E graph and H graph have bipartition classes of equal sizes but are nonhamiltonian.

Classes of connected graphs that are nonhamiltonian include barbell graphs, gear graphs, helm graphs, hypohamiltonian graphs, kayak paddle graphs, lollipop graphs, Menger sponge graphs of positive order, pan graphs, nontrivial path graphs, snarks, nontrivial star graphs, sunlet graphs, tadpole graphs, nontrivial trees, weak snarks, web graphs obtained by removing an outer graph cycle from a stacked prism graph, and windmill graphs formed from at least two copies of a complete graph K_n with n>=2.

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 nonhamiltonian simple 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 nonhamiltonian simple graphs, including disconnected 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 graphs that are nonhamiltonian.

graph G|V(G)|
claw graph4
theta-0 graph7
Petersen graph P10
Herschel graph11
no perfect matching graph16
first Blanuša snark18
second Blanuša snark18
flower snark J_520
Coxeter graph28
double star snark30
Thomassen graph34
Tutte graph46
Szekeres snark50
Meredith graph70

See also

Bicubic Nonhamiltonian Graph, Cubic Nonhamiltonian Graph, Hamiltonian Graph, Horton Graphs, Maximally Nonhamiltonian Graph, Nonhamiltonian Vertex-Transitive Graph, Perihamiltonian Graph, Platypus Graph, Quartic Nonhamiltonian Graph, Quintic Nonhamiltonian Graph, Snark, Tait's Hamiltonian Graph Conjecture, Tutte Bicubic Graph Conjecture, Tutte 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." https://web.archive.org/web/20081004205049/http://people.csse.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 Resource. https://mathworld.wolfram.com/NonhamiltonianGraph.html

Subject classifications