TOPICS
Search

Cubic Nonhamiltonian Graph

NonhamiltonianCubicGraphs

Cubic nonhamiltonian graphs are nonhamiltonian graphs that are also cubic. The numbers of connected cubic nonhamiltonian graphs on n=10, 12, ... nodes are 2, 5, 35, 219, 1666, ... (OEIS A164919). The figure above shows some nonhamiltonian connected cubic graphs that are not snarks (which are excluded since snarks are necessarily both nonplanar and nonhamiltonian).

TaitsHamiltonianGraphConjecture

Cubic nonhamiltonian graphs are of special interest because of Tait's Hamiltonian graph conjecture. The cubic polyhedral nonhamiltonian graphs illustrated above all provide counterexamples to this conjecture. The smallest possible cubic polyhedral nonhamiltonian graph occurs on 38 nodes. In fact there are exactly six such graphs (Holton and McKay 1988), with the Barnette-Bosák-Lederberg graph being the first discovered. There exists a cubic nonhamiltonian polyhedral graph on n nodes for every even n>=38 (Holton and McKay 1988, van Cleemput and Zamfirescu 2018).

The Horton graphs and Ellingham-Horton graphs are examples of 3-connected bicubic graphs that provide counterexamples to the Tutte conjecture.

Hunter (1962) conjectured that all cyclically 5-connected polyhedral graphs contain a Hamiltonian cycle (Grünbaum 2003, p. 365), but a 162-vertex graph due Walther (1965) provided a counterexample (Grünbaum (2003, pp. 365-366).

The smallest possible size of an untraceable cubic polyhedral graph has between 54 (Knorr 2010) and 88 (Zamfierescu 1980), and it is know that there exists such a graph for every even n>=88 (van Cleemput and Zamfirescu 2018).

All six smallest cubic nonhamiltonian polyhedral graphs are platypus graphs (Goedgebeur et al. 2020).

See also

Barnette-Bosák-Lederberg graph, Bicubic Nonhamiltonian Graph, Cubic Graph, Horton Graphs, Nonhamiltonian Graph, Quartic Nonhamiltonian Graph, Quintic Nonhamiltonian Graph, Snark, Tait's Hamiltonian Graph Conjecture, Tutte Conjecture, Walther Graphs

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.Goedgebeur, J.; Neyt, A.; and Zamfirescu, C. T. "Structural and Computational Results on Platypus Graphs." Appl. Math. Comput., 386:125491, 10 pages, 2020.Grünbaum, B. Convex Polytopes, 2nd ed. New York: Springer-Verlag, 2003.Holton, D. A. and McKay, B. D. "The Smallest Non-Hamiltonian 3-Connected Cubic Planar Graphs Have 38 Vertices." J. Combin. Th. SeR. B 45, 305-319, 1988.Hunter, H. F. On Non-Hamiltonian Maps and their Duals. Ph. D. thesis. Troy, NY: Rensselaer Polytechnic Institute, 1962.Knorr, P. Aufspannende Kreise und Wege in polytopalen Graphen. PhD thesis. Dortmund, Germany: Universität Dortmund, 2010.Sloane, N. J. A. Sequence A164919, in "The On-Line Encyclopedia of Integer Sequences."van Cleemput, N. and Zamfirescu, C. T. "Regular Non-Hamiltonian Polyhedral Graphs." Appl. Math. Comput. 338 192-206, 2018.Walther, H. "Ein kubischer, planarer, zyklisch fünffach zusammenhängender Graf, der keinen Hamiltonkreis besizt." Wiss. Z. Hochschule Elektrotech. Ilmenau 11, 163-166, 1965.Zamfirescu, T. "Three Small Cubic Graphs with Interesting Hamiltonian Properties." J. Graph Th. 4, 287-292, 1980.

Referenced on Wolfram|Alpha

Cubic Nonhamiltonian Graph

Cite this as:

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

Subject classifications