×
Fujisawa, Jun; Zamfirescu, Carol T.

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

Discrete Appl. Math. 284, 622-625 (2020).
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.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C40 Connectivity

Keywords:

triangulation; separating triangle; non-Hamiltonian; 1-tough

Citations:

Zbl 1387.05141; Zbl 0442.05046
Cite Review PDF
Full Text: DOI

References:

[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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.