Non-Hamiltonian triangulations with distant separating triangles. (English) Zbl 1387.05141

Summary: T. Böhme et al. [Tatra Mt. Math. Publ. 9, 97–102 (1996; Zbl 0857.05065)] asked whether there exists a non-Hamiltonian triangulation with the property that any two of its separating triangles lie at distance at least 1. Two years later, T. Böhme and J. Harant [Discrete Math. 191, No. 1–3, 25–30 (1998; Zbl 0958.05085)] answered this in the affirmative, showing that for any non-negative integer \(d\) there exists a non-hamiltonian triangulation with seven separating triangles every two of which lie at distance at least \(d\). In this note we prove that the result holds if we replace seven with six, remarking that no non-hamiltonian triangulation with fewer than six separating triangles is known.


05C45 Eulerian and Hamiltonian graphs
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] Böhme, T.; Harant, J.; Tkáč, M., On certain Hamiltonian cycles in planar graphs, J. Graph Theory, 32, 81-96 (1999) · Zbl 0931.05047
[4] Chvátal, V., Tough graphs and Hamiltonian circuits, Discrete Math., 306, 910-917 (2006) · Zbl 1095.05021
[5] Jackson, B.; Yu, X., Hamilton cycles in plane triangulations, J. Graph Theory, 41, 138-150 (2002) · Zbl 1012.05106
[6] Nishizeki, T., A 1-tough non-Hamiltonian maximal planar graph, Discrete Math., 30, 305-307 (1980) · Zbl 0442.05046
[7] Thomas, R.; Yu, X., 4-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser. B, 62, 114-132 (1994) · Zbl 0802.05051
[8] Tutte, W. T., A theorem on planar graphs, Trans. Amer. Math. Soc., 82, 99-116 (1956) · Zbl 0070.18403
[9] Whitney, H., A theorem on graphs, Ann. of Math., 32, 378-390 (1931)
[10] Whitney, H., Congruent graphs and the connectivity of graphs, Amer. J. Math., 54, 150-168 (1932)
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.