Contents

-

Small Hypohamiltonian Graphs

R.E.L. Aldred 1, Brendan D. McKay 2, N.C. Wormald 3
1 Department of Mathematics and Statistics University of Otago P.O. Box 56 Dunedin, New Zealand
2Department of Computer Science Australian National University Canberra, A.C.T. 0200, Australia
3Department of Mathematics University of Melbourne Parkville, Victoria 3052, Australia

Abstract

A graph G is said to be \emph{hypohamiltonian} if G is not Hamiltonian but for each vV(G), the vertex-deleted subgraph Gv is Hamiltonian. In this paper, we show that there is no hypohamiltonian graph on 17 vertices and thereby complete the answer to the question, “For which values of n do there exist hypohamiltonian graphs
on n vertices?”. In addition, we present an exhaustive list of hypohamiltonian graphs on fewer than 18 vertices and extend previously obtained results for cubic hypohamiltonian graphs.