Planar Hypohamiltonian Graphs on 40 Vertices

Mohammadreza Jooyandeh, Brendan D. Mckay, Patric R J Östergård, Ville H. Pettersson, Carol T. Zamfirescu

Research output: Contribution to journalArticleScientificpeer-review

12 Citations (Scopus)

Abstract

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer-aided generation of certain families of planar graphs with girth 4 and a fixed number of 4-faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest planar hypohamiltonian graph of girth 5 has 45 vertices.

Original languageEnglish
Pages (from-to)121-133
Number of pages13
JournalJOURNAL OF GRAPH THEORY
Volume84
Issue number2
Early online date2016
DOIs
Publication statusPublished - Feb 2017
MoE publication typeA1 Journal article-refereed

Keywords

  • Graph generation
  • Grinberg's Theorem
  • Hypohamiltonian graph
  • Hypotraceable graph
  • Planar graph

Fingerprint Dive into the research topics of 'Planar Hypohamiltonian Graphs on 40 Vertices'. Together they form a unique fingerprint.

  • Cite this

    Jooyandeh, M., Mckay, B. D., Östergård, P. R. J., Pettersson, V. H., & Zamfirescu, C. T. (2017). Planar Hypohamiltonian Graphs on 40 Vertices. JOURNAL OF GRAPH THEORY, 84(2), 121-133. https://doi.org/10.1002/jgt.22015