Skip navigation
Skip navigation

Planar Hypohamiltonian Graphs on 40 Vertices

Jooyandeh, Mohammadreza; McKay, Brendan; Ostergard, Patric R. J.; Pettersson, Ville H.; Zamfirescu, Carol T.


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...[Show more]

CollectionsANU Research Publications
Date published: 2017
Type: Journal article
Source: Journal of Graph Theory
DOI: 10.1002/jgt.22015


File Description SizeFormat Image
01_Jooyandeh_Planar_Hypohamiltonian_Graphs_2017.pdf527.68 kBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator