##
**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.

### MSC:

05C45 | Eulerian and Hamiltonian graphs |

05C10 | Planar graphs; geometric and topological aspects of graph theory |

05C38 | Paths and cycles |

### Citations:

Zbl 0802.05051
PDF
BibTeX
XML
Cite

\textit{K. Ozeki} and \textit{C. T. Zamfirescu}, SIAM J. Discrete Math. 32, No. 4, 2783--2794 (2018; Zbl 1401.05175)

Full Text:
DOI

### 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 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.