×
Ozeki, Kenta; Zamfirescu, Carol T.

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

Discrete Math. 341, No. 7, 1900-1902 (2018).
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.

Cited in 1 Review
Cited in 2 Documents

MSC:

05C45 Eulerian and Hamiltonian graphs

Keywords:

triangulation; separating triangle; non-Hamiltonian

Citations:

Zbl 0857.05065; Zbl 0958.05085
PDF BibTeX XML Cite
\textit{K. Ozeki} and \textit{C. T. Zamfirescu}, Discrete Math. 341, No. 7, 1900--1902 (2018; Zbl 1387.05141)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

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] 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) · JFM 57.0727.03
[10] 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.