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

Ozeki, Kenta; Zamfirescu, Carol T.

SIAM J. Discrete Math. 32, No. 4, 2783-2794 (2018).

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.

MSC:

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

Keywords:

Hamiltonian cycle; crossing number; 3-cuts

Citations:

Zbl 0802.05051

References:

[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.
[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.
[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. · JFM 57.0727.03
[17]	C. T. Zamfirescu, Cubic vertices in planar hypohamiltonian graphs, J. Graph Theory, to appear. · Zbl 1120.05054