Cubic nonhamiltonian graphs are nonhamiltonian graphs that are also cubic. The numbers of connected
cubic nonhamiltonian graphs on , 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).
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 (the Barnette-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).
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 untraceablecubicpolyhedral 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).
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. 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. Ilmenau11,
163-166, 1965.Zamfirescu, T. "Three Small Cubic Graphs with Interesting
Hamiltonian Properties." J. Graph Th.4, 287-292, 1980.