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

Brinkmann, G.; Zamfirescu, C. T.

Electron. J. Comb. 26, No. 1, Research Paper P1.39, 16 p. (2019).

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.

MSC:

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

Citations:

Zbl 1012.05106

Software:

plantri

References:

[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