Metraipolis › archive › dc_0f69e2f985f8

Local modifications in planar hypohamiltonian graphs — arXiv:2610.21210

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.21210
License (as archived)
CC0-1.0
Archived
2026-10-16T10:33:24.577Z
SHA-256 of the archived text
5a4f479cb2855ab68aecf51850340af2f700f91fabeb0a76d440de176674b74c
Stable URL of this page
https://metraipolis.com/documento/dc_0f69e2f985f8

How to cite

Local modifications in planar hypohamiltonian graphs — arXiv:2610.21210 — arXiv (en), https://arxiv.org/abs/2610.21210 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0f69e2f985f8 (Metraipolis archive dc_0f69e2f985f8, sha256 5a4f479cb2855ab68aecf51850340af2f700f91fabeb0a76d440de176674b74c)
BibTeX
@misc{dc0f69e2f985f8,
  title = {Local modifications in planar hypohamiltonian graphs — arXiv:2610.21210},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.21210},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0f69e2f985f8; sha256 5a4f479cb2855ab68aecf51850340af2f700f91fabeb0a76d440de176674b74c},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.21210. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We prove that for $n \geq 36$ there exists a planar hypohamiltonian graph of order $n$. As a corollary, we prove that for $n \geq 33$ there exists an almost hypohamiltonian planar graph of order $n$. Further, we exhibit over 100 planar hypohamiltonian graphs of order less than 40, including new graphs of orders 36, 37, 38, and 39. The proof utilizes three local modifications that alter a graph $G$ by removing a subgraph $H$ and replacing it with $H'$ to form a new graph $G'$: a plus two modification, a plus three modification, and Thomassen's iterable plus four modification. The plus two modification preserves hypohamiltonicity in general, and the plus three modification preserves hypohamiltonicity in our cases of interest. This establishes the main result beginning with Tsai's order 34 examples. Further, we conjecture that among planar hypohamiltonian graphs, Tsai's 34 vertex examples are the smallest order. The conjecture is based on previous results, constraints on the degree modulo 3, and experimentation with planar graphs consisting entirely of 4-gons and 5-gons.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.21210 — 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-16T08:50:47.571Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).