Toughness and Vertex Degrees
Douglas C. Bauer, Hajo J. Broersma, Jan van den Heuvel, Nathan Kahl, Edward F. Schmeichel · Journal of Graph Theory · 2012
Abstract We study theorems giving sufficient conditions on the vertex degrees of a graph G to guarantee G is t‐tough. We first give a best monotone theorem when , but then show that for any integer , a best monotone theorem for requires at least nonredundant conditions, where grows superpolynomially as . When , we give an additional, simple theorem for G to be t‐tough, in terms of its vertex degrees.