Planar hypohamiltonian graphs on 40 vertices. (English) Zbl 1356.05029

Summary: A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to M. Araya and G. Wiener [Electron. J. Comb. 18, No. 1, Research Paper P85, 11 p. (2011; Zbl 1217.05065)]. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer-aided generation of certain families of planar graphs with girth 4 and a fixed number of 4-faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest planar hypohamiltonian graph of girth 5 has 45 vertices.


05C10 Planar graphs; geometric and topological aspects of graph theory
05C45 Eulerian and Hamiltonian graphs


Zbl 1217.05065


House of Graphs
Full Text: DOI arXiv


[1] R. E. L.Aldred, B. D.McKay, and N. C.Wormald, Small hypohamiltonian graphs, J Combin Math Combin Comput23 (1997), 143-152. · Zbl 0880.05061
[2] M.Araya and G.Wiener, On cubic planar hypohamiltonian and hypotraceable graphs, Electron J Combin18(1) (2011), #P85. · Zbl 1217.05065
[3] G.Brinkmann, K.Coolsaet, J.Goedgebeur, and H.Mélot, House of graphs: A database of interesting graphs, Discrete Appl Math161 (2013), 311-314. http://hog.grinvin.org. · Zbl 1292.05254
[4] G.Brinkmann and B. D.McKay, Construction of planar triangulations with minimum degree 5, Discrete Math301 (2005), 147-163. · Zbl 1078.05022
[5] V.Chvátal, Flip‐flops in hypohamiltonian graphs, Can Math Bull16 (1973), 33-41. · Zbl 0253.05142
[6] E. J.Grinberg, Plane homogeneous graphs of degree three without Hamiltonian circuits, Latvian Math Yearbook4 (1968), 51-58. · Zbl 0185.27901
[7] B.Grünbaum, Vertices missed by longest paths or circuits, J Combin Theory Ser A17 (1974), 31-38. · Zbl 0259.05120
[8] W.Hatzel, Ein planarer hypohamiltonscher Graph mit 57 Knoten, Math Ann243 (1979), 213-216. · Zbl 0396.05032
[9] M.Jooyandeh, Planar hypohamiltonian graphs data. http://www.jooyandeh.com/planar_hypo.
[10] A.Shabbir, C. T.Zamfirescu, and T. I.Zamfirescu, Intersecting longest paths and longest cycles: A survey, Electron J Graph Theory Appl1 (2013), 56-76. · Zbl 1306.05121
[11] C.Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Math9 (1974), 91-96. · Zbl 0278.05110
[12] C.Thomassen, On hypohamiltonian graphs, Discrete Math10 (1974), 383-390. · Zbl 0286.05122
[13] C.Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math14 (1976), 377-389. · Zbl 0322.05130
[14] C.Thomassen, Hypohamiltonian graphs and digraphs, In: Theory and Applications of Graphs, vol. 642 of Lecture Notes in Mathematics (Y.Alavi (ed.) and D.Lick (ed.), Eds.), Springer, Berlin/Heidelberg, 1978, pp. 557-571. · Zbl 0371.05015
[15] C.Thomassen, Planar cubic hypohamiltonian and hypotraceable graphs, J Combin Theory Ser B30 (1981), 36-44. · Zbl 0388.05033
[16] D. B.West, Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River, New Jersey, USA, 2001.
[17] G.Wiener and M.Araya, On planar hypohamiltonian graphs, J Graph Theory67 (2011), 55-68. · Zbl 1223.05168
[18] J.Zaks, Non‐Hamiltonian non‐Grinbergian graphs, Discrete Math17 (1977), 317-321. · Zbl 0357.05052
[19] C. T.Zamfirescu and T. I.Zamfirescu, A planar hypohamiltonian graph with 48 vertices, J Graph Theory55 (2007), 338-342. · Zbl 1120.05054
[20] T.Zamfirescu, A two‐connected planar graph without concurrent longest paths, J Combin Theory Ser B13 (1972), 116-121. · Zbl 0243.05110
[21] T.Zamfirescu, On longest paths and circuits in graphs, Math Scand38 (1976), 211-239. · Zbl 0337.05127
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.