On Smallest Maximally Nonhamiltonian Graphs

Abstract

Bollobas posed the problem of finding the least number of edges, $f(n)$, in a maximally nonhamiltonian graph of order $n$. Clark, Entringer and Shapiro showed $f(n)=\lceil \frac{3n}{2}\rceil$ for all even $n\ge 36$ and all odd $n\ge 53$. In this paper, we give the values of $f(n)$ for all $n\ge 3$ and show $f(n)=\lceil \frac{3n}{2}\rceil$ for all even $n\ge 20$ and odd $n\ge 17$.