Polyhedra with few 3-cuts are Hamiltonian. (English) Zbl 1409.05122

Summary: In 1956, Tutte showed that every planar 4-connected graph is Hamiltonian. In this article, we will generalize this result and prove that polyhedra with at most three \(3\)-cuts are Hamiltonian. In [J. Graph Theory 41, No. 2, 138–150 (2002; Zbl 1012.05106)], B. Jackson and X. Yu have shown this result for the subclass of triangulations. We also prove that polyhedra with at most four \(3\)-cuts have a Hamiltonian path. It is well known that for each \(k\geq 6\) non-Hamiltonian polyhedra with \(k\) \(3\)-cuts exist. We give computational results on lower bounds on the order of a possible non-Hamiltonian polyhedron for the remaining open cases of polyhedra with four or five \(3\)-cuts.


05C45 Eulerian and Hamiltonian graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C40 Connectivity
52B10 Three-dimensional polytopes


Zbl 1012.05106


Full Text: arXiv Link


[1] G. Brinkmann and B.D. McKay. Fast generation of planar graphs. MATCH Commun. Math. Comput. Chem., 58(2):323–357, 2007.Seehttp://cs.anu.edu.au/  bdm/index.html. · Zbl 1164.68025
[2] G. Brinkmann, J. Souffriau, and N. Van Cleemput. On the strongest form of a theorem of Whitney for hamiltonian cycles in plane triangulations. J. Graph Theory, 83(1):78–91, 2016. · Zbl 1346.05149
[3] G. Brinkmann, J. Souffriau, and N. Van Cleemput. On the number of hamiltonian cycles in triangulations with few separating triangles. J. Graph Theory, 87(2):164– 175, 2018. · Zbl 1380.05119
[4] G.R.T. Hendry. Scattering number and extremal non-hamiltonian graphs. Discrete Math., 71:165–175, 1988. · Zbl 0655.05044
[5] B. Jackson and X. Yu. Hamilton cycles in plane triangulations. J. Graph Theory, 41(2):138–150, 2002. · Zbl 1012.05106
[6] D.P. Sanders. On paths in planar graphs. J. Graph Theory, 24(4):341–345, 1997. · Zbl 0880.05059
[7] R. Thomas and X. Yu. 4-connected projective-planar graphs are hamiltonian. J. Comb. Theory B, 1:114–132, 1994. · Zbl 0802.05051
[8] W.T. Tutte. A theorem on planar graphs. Trans. Am. Math. Soc., 82:99–116, 1956. · Zbl 0070.18403
[9] H . Whitney. A theorem on graphs. Ann. Math., 32(2):pp. 378 – 390, 1931. the electronic journal of combinatorics 26(1) (2019), #P1.3916 · JFM 57.0727.03
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.