Maximal Nontraceable Graphs with Toughness less than One

Abstract

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.