# zbMATH — the first resource for mathematics

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.

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