Premium
Hypohamiltonian Planar Cubic Graphs with Girth 5
Author(s) -
McKay Brendan D.
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22043
Subject(s) - combinatorics , mathematics , planar graph , polyhedral graph , cubic graph , planar , vertex (graph theory) , odd graph , discrete mathematics , chordal graph , 1 planar graph , graph , line graph , computer science , voltage graph , computer graphics (images)
A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4‐cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices.