Maximal Nontraceable Graphs with Toughness less than One

Frank Bullock, Marietjie Frick, Joy Singleton, Susan van Aardt, Kieka (C.M.) Mynhardt

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.


Full Text: PDF