Non-Hamiltonian 1-tough triangulations with disjoint separating triangles. (English) Zbl 1443.05108

Summary: In this note, we consider triangulations of the plane. K. Ozeki and C. T. Zamfirescu [Discrete Math. 341, No. 7, 1900–1902 (2018; Zbl 1387.05141)] asked whether there are non-Hamiltonian 1-tough triangulations in which every two separating triangles are disjoint. We answer this question in the affirmative and strengthen a result of T. Nishizeki [ibid. 30, 305–307 (1980; Zbl 0442.05046)] by proving that there are infinitely many non-Hamiltonian 1-tough triangulations with pairwise disjoint separating triangles.


05C45 Eulerian and Hamiltonian graphs
05C40 Connectivity
Full Text: DOI


[1] Böhme, T.; Harant, J., On hamiltonian cycles in 4- and 5-connected plane triangulations, Discrete Math., 191, 25-30 (1998) · Zbl 0958.05085
[2] Böhme, T.; Harant, J.; Tkáč, M., On the minimal number of separating 3-cycles in non-hamiltonian maximal planar graphs, Tatra Mt. Math. Publ., 9, 97-102 (1996) · Zbl 0857.05065
[3] Brinkmann, G.; Zamfirescu, C. T., Polyhedra with few 3-cuts are hamiltonian, Electron. J. Combin., 26, 1, Article P1.39 pp. (2019) · Zbl 1409.05122
[4] Chvátal, V., Tough graphs and hamiltonian circuits, Discrete Math., 5, 215-228 (1973) · Zbl 0256.05122
[5] Dillencourt, M. B., An upper bound on the shortness exponent of 1-tough, maximal planar graphs, Discrete Math., 90, 93-97 (1991) · Zbl 0729.05029
[6] Jackson, B.; Yu, X., Hamilton cycles in plane triangulations, J. Graph Theory, 41, 138-150 (2002) · Zbl 1012.05106
[7] Nishizeki, T., A 1-tough nonhamiltonian maximal planar graph, Discrete Math., 30, 305-307 (1980) · Zbl 0442.05046
[8] Ozeki, K.; Zamfirescu, C. T., Non-hamiltonian triangulations with distant separating triangles, Discrete Math., 341, 1900-1902 (2018) · Zbl 1387.05141
[9] Thomas, R.; Yu, X., 4-connected projective-planar graphs are hamiltonian, J. Combin. Theory, Ser. B, 62, 114-132 (1994) · Zbl 0802.05051
[10] Tkáč, M., On the shortness exponent of 1-tough, maximal planar graphs, Discrete Math., 154, 321-328 (1996) · Zbl 0852.05055
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.