\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
\nopagenumbers
\noindent
%
%
{\bf Marietjie Frick and Joy Singleton }
%
%
\medskip
\noindent
%
%
{\bf Lower Bound for the Size of Maximal Nontraceable Graphs }
%
%
\vskip 5mm
\noindent
%
%
%
%
Let $g(n)$ denote the minimum number of edges of a maximal
nontraceable graph of order $n$.  Dudek, Katona and Wojda (2003)
showed that $ g(n) \geq \lceil {3n-2\over2} \rceil -2$ for $ n \ge
20$ and $ g(n) \le \lceil {3n-2\over2} \rceil$ for $ n \geq 54$ as
well as for $n \in I= \{22,23,30,31,38,39,40,41,42,43,46,$
$47,48,49,50,51\}$.  We show that $ g(n) = \lceil {3n-2\over2}
\rceil$ for $ n \geq 54$ as well as for $n \in I \cup \{12,13\}$ and
we determine $g(n)$ for $n \le 9$.


\bye

.
