Local modifications in planar hypohamiltonian graphs

Abstract

We prove that for n ≥ 36 there exists a planar hypohamiltonian graph of order n. As a corollary, we prove that for n ≥ 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.

Bounds for B-coloring planar and outerplanar graphs
Ryan Martin, Miklós Ruszinkó, Gábor Sárközy
Discrete Mathematics15 Sep 2026Peer-reviewedLicence not statedCombinatorics & discrete mathematicsHAL
Planar graphs whose second largest eigenvalue does not exceed 1
Zihao Geng, Zhiwen Wang, Wen-Jun Li +3
arXiv17 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
A graded version of the separator theorem for planar graphs
Nabil H. Mustafa, Janos Pach
arXiv25 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Treedepth is NP-Hard on Planar Graphs of Maximum Degree 3
Kolja Kühn
arXiv30 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Almost Linear Universal Point Sets for Planar Graphs
Taylor Gordon
arXiv10 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{durias2026local,
  title = {{Local modifications in planar hypohamiltonian graphs}},
  author = {Samantha Durias and Sabrina Guerrero and Briana Jaiyen and Daniel Kaplan and Austin Lapine and Caleb Peralta and Akul Shrivastav},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.21210},
  eprint = {2610.21210},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.21210},
}

RIS

TY  - UNPB
TI  - Local modifications in planar hypohamiltonian graphs
AU  - Samantha Durias
AU  - Sabrina Guerrero
AU  - Briana Jaiyen
AU  - Daniel Kaplan
AU  - Austin Lapine
AU  - Caleb Peralta
AU  - Akul Shrivastav
PY  - 2026
DA  - 2026/10/15
PB  - arXiv
DO  - 10.48550/arxiv.2610.21210
UR  - https://arxiv.org/abs/2610.21210
AB  - We prove that for n ≥ 36 there exists a planar hypohamiltonian graph of order n. As a corollary, we prove that for n ≥ 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.
ER  -

Abstract

Related

Cite