TOPICS
Cubic Nonhamiltonian Graph
Cubic nonhamiltonian graphs arenonhamiltonian graphs that are alsocubic. The numbers of connected cubic nonhamiltonian graphs on
, 12, ... nodes are 2, 5, 35, 219, 1666, ... (OEISA164919). The figure above shows some nonhamiltonian connected cubic graphs that are notsnarks (which are excluded since snarks are necessarily bothnonplanar andnonhamiltonian).
Cubic nonhamiltonian graphs are of special interest because ofTait'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 (theBarnette-Bosák-Lederberg graph), and there exists a cubic polyhedral nonhamiltonian graph on
nodes for every even
(Holton and McKay 1988, van Cleemput and Zamfirescu 2018).
TheHorton graphs and Ellingham-Horton graphs are examples of 3-connectedbicubic graphs that provide counterexamples to theTutte conjecture.
Hunter (1962) conjectured that all cyclically 5-connected polyhedral graphs contain aHamiltonian 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 anuntraceablecubicpolyhedral graph has between 54 (Knorr 2010) and 88 (Zamfierescu 1980), and it is know that there exists such a graph for every even
(van Cleemput and Zamfirescu 2018).
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 GraphsExplore 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.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. B45, 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. SequenceA164919, 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. Ilmenau11, 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 GraphCite this as:
Weisstein, Eric W. "Cubic Nonhamiltonian Graph."FromMathWorld--A Wolfram Resource.https://mathworld.wolfram.com/CubicNonhamiltonianGraph.html