Menu
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) \leq \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.