Every 4-connected graph with crossing number 2 is Hamiltonian. (English) Zbl 1401.05175

Summary: A seminal theorem of Tutte states that 4-connected planar graphs are Hamiltonian. Applying a result of R. Thomas and X. Yu [J. Comb. Theory, Ser. B 62, No. 1, 114–132 (1994; Zbl 0802.05051)], one can show that every 4-connected graph with crossing number 1 is Hamiltonian. In this paper, we continue along this path and prove the titular statement. We also discuss the traceability and Hamiltonicity of 3-connected graphs with small crossing number and few 3-cuts, and present applications of our results.


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


Zbl 0802.05051
Full Text: DOI


[1] G. Brinkmann and C. T. Zamfirescu, Polyhedra with Few 3-Cuts are Hamiltonian, preprint, arXiv:1606.01693 [math.CO], 2016.
[2] B. Grünbaum, Polytopes, graphs and complexes, Bull. Amer. Math. Soc., 76 (1970), pp. 1131–1201. · Zbl 0211.25001
[3] B. Jackson and X. Yu, Hamilton cycles in plane triangulations, J. Graph Theory, 41 (2002), pp. 138–150. · Zbl 1012.05106
[4] K. Kawarabayashi and K. Ozeki, \(4\)-connected projective-planar graphs are Hamiltonian-connected, J. Combin. Theory Ser. B, 112 (2015), pp. 36–69. · Zbl 1310.05132
[5] C. St. J. A. Nash-Williams, Unexplored and semi-explored territories in graph theory, in New Directions in the Theory of Graphs, Academic Press, New York, 1973, pp. 149–186. · Zbl 0263.05101
[6] K. Ozeki, N. Van Cleemput, and C. T. Zamfirescu, Hamiltonian properties of polyhedra with few 3-cuts—A survey, Discrete Math., 341 (2018), pp. 2646–2660. · Zbl 1392.05066
[7] R. B. Richter and G. Salazar, Crossing numbers, in Handbook of Graph Theory, 2nd ed., J. L. Gross, J. Yellen, and P. Zhang, eds., Chapman and Hall, Boca Raton, FL, 2013.
[8] D. P. Sanders, On Hamilton cycles in certain planar graphs, J. Graph Theory, 21 (1996), pp. 43–50. · Zbl 0839.05068
[9] D. P. Sanders, On paths in planar graphs, J. Graph Theory, 24 (1997), pp. 341–345. · Zbl 0880.05059
[10] R. Thomas and X. Yu, 4-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser. B, 62 (1994), pp. 114–132. · Zbl 0802.05051
[11] R. Thomas, X. Yu, and W. Zang, Hamilton paths in toroidal graphs, J. Combin. Theory Ser. B, 94 (2005), pp. 214–236. · Zbl 1066.05082
[12] C. Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math., 14 (1976), pp. 377–389. · Zbl 0322.05130
[13] C. Thomassen, Hypohamiltonian graphs and digraphs, in Proceedings of the International Conference on Theory and Application of Graphs, Kalamazoo, 1976, Lecture Notes in Comput. Sci. 642, Springer, Berlin, 1978, pp. 557–571. · Zbl 0371.05015
[14] C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory, 7 (1983), pp. 169–176. · Zbl 0515.05040
[15] W. T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc., 82 (1956), pp. 99–116. · Zbl 0070.18403
[16] H. Whitney, A theorem on graphs, Ann. Math. (2), 32 (1931), pp. 378–390.
[17] C. T. Zamfirescu, Cubic vertices in planar hypohamiltonian graphs, J. Graph Theory, to appear. · 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.