\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Frank Bullock, Marietjie Frick, Joy Singleton, Susan van Aardt and Kieka (C.M.) Mynhardt}
%
%
\medskip
\noindent
%
%
{\bf Maximal Nontraceable Graphs with Toughness less than One }
%
%
\vskip 5mm
\noindent
%
%
%
%
A graph $G$ is maximal nontraceable (MNT) if $G$ does not have a
hamiltonian path but, for every $e\in E\left( \overline{G}\right) $, the
graph $G+e$ has a hamiltonian path. A graph $G$ is 1-tough if for every
vertex cut $S$ of $G$ the number of components of $G-S$ is at most $|S|$. We
investigate the structure of MNT graphs that are not 1-tough. Our results
enable us to construct several interesting new classes of MNT graphs. 

\bye

.
