1973/03/01 by Vašek Chvátal · 58 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications #Combinatorics #Mathematics #Cubic graph #Petersen graph #Coxeter graph #Symmetric graph #Discrete mathematics #Graph #Voltage graph #Line graph
paper · pdf · doi:10.4153/cmb-1973-008-9
published in Canadian Mathematical Bulletin 16(1), 33-41 (Cambridge University Press)
openalex publication_date 1973/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
Throughout this note, we adopt the graph-theoretical terminology and notation of Harary [3]. A graph G is hypohamiltonian if G is not hamiltonian but the deletion of any point u from G results in a hamiltonian graph G-u . Gaudin, Herz, and Rossi [2] proved that the smallest hypohamiltonian graph is the Petersen graph. Using a computer for a systematic search, Herz, Duby, and Vigué [4] found that there is no hypohamiltonian graph with 11 or 12 points. However, they found one with 13 and one with 15 points. Sousselier [4] and Lindgren [5] constructed independently the same sequence of hypohamiltonian graphs with 6k+10 points. Moreover, Sousselier found a cubic hypohamiltonian graph with 18 points. This graph and the Petersen graph were the only examples of cubic hypohamiltonian graphs until Bondy [1] constructed an infinite sequence of cubic hypohamiltonian graphs with 12 k +10 points. Bondy also proved that the Coxeter graph [6], which is cubic with 28 points, is hypohamiltonian.