Hypohamiltonian Planar Cubic Graphs with Girth 5

Brendan D. McKay*

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    7 Citations (Scopus)

    Abstract

    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.

    Original languageEnglish
    Pages (from-to)7-11
    Number of pages5
    JournalJournal of Graph Theory
    Volume85
    Issue number1
    DOIs
    Publication statusPublished - 1 May 2017

    Fingerprint

    Dive into the research topics of 'Hypohamiltonian Planar Cubic Graphs with Girth 5'. Together they form a unique fingerprint.

    Cite this