Properties of $1$-Tough Graphs

Abstract

A graph $G$ is defined by Chvátal $[4]$ to be $n$ $tough$ if, given any set of vertices $S,S\subseteq G$, $c(G–S)\le \frac{|S|}{n}$. We present several results relating to the recognition and construction of $1$-tough graphs, including the demonstration that all $n$-regular, $n$-connected graphs are $1$-tough. We introduce the notion of minimal $1$-tough graphs, and tough graph augmentation, and present results relating to these topics.