×

zbMATH — the first resource for mathematics

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

MSC:
05C45 Eulerian and Hamiltonian graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
PDF BibTeX XML Cite
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.