2015/07/26 by Brendan D. McKay, McKay, Brendan D.
Computer Science · Engineering · Mathematics · #05C45 05C10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #graph theory and CDMA systems #math.CO #msc:05C10 #msc:05C45
paper · pdf · doi:10.48550/arxiv.1507.07197
arxiv created 2015/07/26 · openalex publication_date 2015/07/26 · arxiv updated 2015/07/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 five, and thus girth five. We show by computer search that the smallest members of this class are three graphs with 76 vertices.