Toughness and Vertex Degrees

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 $t\ge 1$, but then show that for any integer $k\ge 1$, a best monotone theorem for $t=\frac{1}{k}\le 1$ requires at least $f(k)\cdot |V(G)|$ nonredundant conditions, where $f(k)$ grows superpolynomially as $k\to \infty$. When $t<1$, we give an additional, simple theorem for $G$ to be $t$-tough, in terms of its vertex degrees.

13 pages