Metraipolis › archive › dc_a90e8f564fee
Non-Hamiltonian $\frac{3}{2}$-Tough Plane Triangulations — arXiv:2609.05414
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.05414
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T23:21:23.658Z
- SHA-256 of the archived text
85057fa18b68c4bd9271dfc239f9905343a09d8c7d616b41e5c7b5e5c093bec7- Stable URL of this page
https://metraipolis.com/documento/dc_a90e8f564fee
How to cite
Non-Hamiltonian $\frac{3}{2}$-Tough Plane Triangulations — arXiv:2609.05414 — arXiv (en), https://arxiv.org/abs/2609.05414 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a90e8f564fee (Metraipolis archive dc_a90e8f564fee, sha256 85057fa18b68c4bd9271dfc239f9905343a09d8c7d616b41e5c7b5e5c093bec7)
BibTeX
@misc{dca90e8f564fee,
title = {Non-Hamiltonian $frac32$-Tough Plane Triangulations — arXiv:2609.05414},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.05414},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a90e8f564fee; sha256 85057fa18b68c4bd9271dfc239f9905343a09d8c7d616b41e5c7b5e5c093bec7},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.05414. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
By Tutte's classic theorem of 1956 that every 4-connected planar graph is Hamiltonian, every planar graph of order at least three with toughness greater than $\frac{3}{2}$ is Hamiltonian. In 1999, Owens constructed a sequence of maximal planar graphs whose toughness approaches $\frac{3}{2}$ from below and which do not contain even a 2-factor, and he asked whether there exists a maximal planar graph with toughness exactly $\frac{3}{2}$ and with no 2-factor. In 2025, Shan constructed a $\frac{3}{2}$-tough plane triangulation with no 2-factor. In that construction, there are many pairs of vertices of degree $3$ that have a common neighbor. By imposing a distance condition on the vertices of degree $3$, Hao, Ma, Shan, and Yang recently proved that every $\frac{3}{2}$-tough plane triangulation of order at least three whose vertices of degree $3$ are pairwise at distance at least $3$ has a 2-factor, and they asked whether every such graph is Hamiltonian. We answer this question in the negative, and in fact prove the following stronger statement: for every positive integer $\ell$, there exists a $\frac{3}{2}$-tough non-Hamiltonian plane triangulation whose vertices of degree $3$ are pairwise at distance at least $\ell$. Thus, although the distance condition guarantees the existence of a 2-factor, it does not guarantee that the graph is Hamiltonian: the essential obstruction to a Hamiltonian cycle is a certain local configuration involving a vertex of degree $3$, rather than the proximity of such configurations in the graph.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-07 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.05414 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T23:03:13.274Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).