Toughness and Vertex Degrees

الأصل · EN

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 t≥1, but then show that for any integer k≥1, a best monotone theorem for t=1k≤ 1 requires at least f(k)·|V(G)| nonredundant conditions, where f(k) grows superpolynomially as k→∞. When t<1, we give an additional, simple theorem for G to be t-tough, in terms of its vertex degrees.