Smallest maximally nonhamiltonian graphs

A graphG ismaximally nonhamiltonian iffG is not hamiltonian butG + e is hamiltonian for each edgee inG ^c, i.e., any two non-adjacent vertices ofG are ends of a hamiltonian path. Bollobás posed the problem of finding the least number of edges,f(n), possible in a maximally nonhamiltonian graph of ordern. Results of Bondy show thatf(n) 3/2 n forn 7. We exhibit graphs of even ordern 36 for which the bound is attained. These graphs are the snarks,J _k, of Isaacs and mild variations of them. For oddn 55 we construct graphs from the graphsJ _k showing that in this case,f(n) = 3n + 1/2 or 3n + 3/2 and leave the determination of which is correct as an open problem. Finally we note that the graphsJ _k, k 7 are hypohamiltonian cubics with girth 6.