On hypohamiltonian and almost hypohamiltonian graphs. (English) Zbl 1312.05076

Summary: A graph \(G\) is almost hypohamiltonian if \(G\) is non-Hamiltonian, there exists a vertex \(w\) such that \(G-v\) is non-Hamiltonian, and for any vertex \(v\neq w\) the graph \(G-v\) is Hamiltonian. We prove the existence of an almost hypohamiltonian graph with 17 vertices and of a planar such graph with 39 vertices. Moreover, we find a 4-connected almost hypohamiltonian graph, while Thomassen’s question whether 4-connected hypohamiltonian graphs exist remains open. We construct planar almost hypohamiltonian graphs of order \(n\) for every \(n\geq 74\). During our investigation we draw connections between hypotraceable, hypohamiltonian, and almost hypohamiltonian graphs, and discuss a natural extension of almost hypohamiltonicity. Finally, we give a short argument disproving a conjecture of Chvátal (originally disproved by Thomassen), strengthen a result of Araya and Wiener on cubic planar hypohamiltonian graphs, and mention open problems.


05C45 Eulerian and Hamiltonian graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
Full Text: DOI Link


[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 (2011), #P85. · Zbl 1217.05065
[3] J. A.Bondy, Variations on the Hamiltonian Theme, Canad Math Bull15 (1972), 57-62. · Zbl 0238.05115
[4] V.Chvátal, Flip‐flops in hypohamiltonian graphs, Canad Math Bull16 (1973), 33-41. · Zbl 0253.05142
[5] V.Chvátal, D. A.Klarner, and D. E.Knuth, Selected Combinatorial Research Problems, STAN‐CS‐72‐292, Stanford Univ., CA, 1972.
[6] J. B.Collier and E. F.Schmeichel, New flip‐flop constructions for hypohamiltonian graphs, Discrete Math18 (1977), 265-271. · Zbl 0367.05046
[7] J. B.Collier and E. F.Schmeichel, Systematic searches for hypohamiltonian graphs, Networks8 (1978), 193-200. · Zbl 0384.05046
[8] T.Gaudin, J.‐C.Herz, and P.Rossi, Solution de problème no. 29, Rev Franç Rech Opérat8 (1964), 214-218.
[9] E. J.Grinberg, Plane homogeneous graphs of degree three without Hamiltonian circuits, Latvian Math Yearbook4 (1968), 51-58 (in Russian). · Zbl 0185.27901
[10] M.Grötschel, On the monotone symmetric travelling salesman problem: hypohamiltonian/hypotraceable graphs and facets, Math Oper Res5 (1980), 285-292. · Zbl 0442.90070
[11] B.Grünbaum, Vertices missed by longest paths or circuits, J Combin Theory, Ser A17 (1974), 31-38. · Zbl 0259.05120
[12] W.Hatzel, Ein planarer hypohamiltonscher Graph mit 57 Knoten, Math Ann243 (1979), 213-216. · Zbl 0396.05032
[13] R.Häggkvist, Problem 443. Special case of the Fulkerson Conjecture. In: ‘Research problems from the 5th Slovenian Conference’, Bled, 2003 (B. Mohar, R. J. Nowakowski, and D. B. West, Eds.). Discrete Math307 (2007), 650-658. · Zbl 1109.05102
[14] D. A.Holton and B. D.McKay, The smallest non‐hamiltonian 3‐connected cubic planar graphs have 38 vertices, J Combin Theory, Ser B45 (1988), 315-319. · Zbl 0607.05051
[15] D. A.Holton and J.Sheehan, The Petersen Graph, Chapter 7: Hypohamiltonian graphs, Cambridge University Press, New York, 1993. · Zbl 0781.05001
[16] J. D.Horton, A Hypotraceable Graph. Research Report CORR 73-4, Dept. Combin. and Optim., Univ. Waterloo, 1973.
[17] M.Jooyandeh, B. D.McKay, P. R. J.Östergård, V. H.Pettersson, and C. T.Zamfirescu, Planar hypohamiltonian graphs on 40 vertices. Submitted.
[18] S. F.Kapoor, H. V.Kronk, and D. R.Lick, On detours in graphs, Canad Math Bull11 (1968), 195-201. · Zbl 0167.22002
[19] E.Máčajová and M.Škoviera, Infinitely many hypohamiltonian cubic graphs of girth 7, Graphs Combin27 (2011), 231-241. · Zbl 1235.05085
[20] J.Park, H.Lim, and H.Kim, Panconnectivity and pancyclicity of hypercube‐like interconnection networks with faulty elements, Theoret Comput Sci377 (2007), 170-180. · Zbl 1115.68116
[21] R.Sousselier, Problème no. 29: Le cercle des irascibles, Rev Franç Rech Opérat7 (1963), 405-406.
[22] C.Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Math9 (1974), 91-96. · Zbl 0278.05110
[23] C.Thomassen, On hypohamiltonian graphs, Discrete Math10 (1974), 383-390. · Zbl 0286.05122
[24] C.Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math14 (1976), 377-389. · Zbl 0322.05130
[25] C.Thomassen, Hypohamiltonian graphs and digraphs, Theory and Applications of Graphs, Lecture Notes in Mathematics 642, Springer, Berlin, 1978, pp. 557-571. · Zbl 0371.05015
[26] C.Thomassen, Planar cubic hypohamiltonian and hypotraceable graphs, J Combin Theory, Ser B30 (1981), 36-44. · Zbl 0388.05033
[27] W. T.Tutte, On hamiltonian circuits, J London Math Soc21 (1946), 98-101. · Zbl 0061.41306
[28] W. T.Tutte, A theorem on planar graphs, Trans Amer Math Soc82 (1956), 99-116. · Zbl 0070.18403
[29] D. B.West, Introduction to Graph Theory, 2nd edn., Prentice Hall, Upper Saddle River, NJ, 2001.
[30] G.Wiener and M.Araya, On planar hypohamiltonian graphs, J Graph Theory67 (2011), 55-68. · Zbl 1223.05168
[31] C. T.Zamfirescu, Hypohamiltonian graphs and their crossing number, Electron J Combin19 (2012), #P12. · Zbl 1266.05079
[32] C. T.Zamfirescu and T. I.Zamfirescu, A planar hypohamiltonian graph with 48 vertices, J Graph Theory55 (2007), 338-342. · Zbl 1120.05054
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.