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).