Infinitely many planar cubic hypohamiltonian graphs of girth 5. (English) Zbl 1391.05153

Summary: A graph \(G\) is hypohamiltonian if \(G\) is non-Hamiltonian and for every vertex \(v\) in \(G\), the graph \(G-v\) is Hamiltonian. B. D. McKay [J. Graph Theory 85, No. 1, 7–11 (2017; Zbl 1365.05064)] asked whether infinitely many planar cubic hypohamiltonian graphs of girth 5 exist. We settle this question affirmatively.


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


Zbl 1365.05064
Full Text: DOI Link


[1] G. M.Adel’son‐Vel’skiǐ and V. K.Titov, On edge 4‐chromatic cubic graphs (in Russian), in Proc. Seminar of 1971 at Moscow Univ., Voprosy Kibernetiki [vol. not numbered], 1973, pp. 5-14.
[2] M.Araya and G.Wiener, On cubic planar hypohamiltonian and hypotraceable graphs, Electronic J. Combin.18 (2011), #P85. · Zbl 1217.05065
[3] A.Cavicchioli et al., Special classes of snarks. Acta Applicandae Mathematica76(1) (2003), 57-88. · Zbl 1018.05033
[4] V.Chvátal, Flip‐flops in hypohamiltonian graphs, Canadian Math. Bull.16(1) (1973), 33-41. · Zbl 0253.05142
[5] S.Fiorini, Hypohamiltonian snarks, Graphs and Other Combinatorial Topics (M.Fiedler (ed.), ed.), volume 59, Teubner, Leipzig, 1983, pp. 70-75. · Zbl 0535.05045
[6] J.Goedgebeur and C. T.Zamfirescu, Improved bounds for hypohamiltonian graphs. Ars Mathematica Contemporanea13(2) (2017), 235-257. · Zbl 1380.05034
[7] J.Goedgebeur and C. T.Zamfirescu, On hypohamiltonian snarks and a theorem of Fiorini, Ars Mathematica Contemporanea14(2) (2018), 227-249. · Zbl 1395.05044
[8] D. A.Holton and J.Sheehan, The Petersen graph, Chapter 7: Hypohamiltonian graphs, Cambridge University Press, Cambridge, 1993. · Zbl 0781.05001
[9] J. D.Horton, A hypotraceable graph. Research Report CORR 73-4, Dept. Combin. and Optim., Univ. Waterloo, 1973.
[10] R.Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable, Am. Math. Monthly82(3) (1975), 221-239. · Zbl 0311.05109
[11] M.Jooyandeh et al. Planar hypohamiltonian graphs on 40 vertices, J. Graph Theory84(2) (2017), 121-133. · Zbl 1356.05029
[12] B. D.McKay, Hypohamiltonian planar cubic graphs with girth 5, J. Graph Theory85(1) (2017), 7-11. · Zbl 1365.05064
[13] K.Ozeki and P.Vrána, 2‐edge‐Hamiltonian‐connectedness of 4‐connected plane graphs, Eur. J. Comb.35 (2014), 432-448. · Zbl 1296.05116
[14] Z.Skupień, Multi‐compositions in exponential counting of hypohamiltonian snarks, Convexity and Discrete Geometry Including Graph Theory, Springer Proc. in Math. & Stat. (K.Adiprasito (ed.), I.Bárány (ed.), C.Vîlcu (ed.), eds.), volume 148, Springer, Cham, 2016, pp. 47-58. · Zbl 1369.05017
[15] R.Sousselier, Problème no. 29: Le cercle des irascibles (in French), Revue Française de Recherche Opérationnelle7 (1963), 405-406.
[16] C.Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math.14(4) (1976), 377-389. · Zbl 0322.05130
[17] G.Wiener, Leaf‐critical and leaf‐stable graphs, J. Graph Theory84(4) (2017), 443-459. · Zbl 1359.05072
[18] C. T.Zamfirescu, On hypohamiltonian and almost hypohamiltonian graphs, J. Graph Theory79(1) (2015), 63-81. · Zbl 1312.05076
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.