Toughness and vertex degrees
Bauer, D., Broersma, H. J., van den Heuvel, J.
, Kahl, N. & Schmeichel, E.
(2013).
Toughness and vertex degrees.
Journal of Graph Theory,
72(2), 209-219.
https://doi.org/10.1002/jgt.21639
, Kahl, N. & Schmeichel, E.
(2013).
Toughness and vertex degrees.
Journal of Graph Theory,
72(2), 209-219.
https://doi.org/10.1002/jgt.21639
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\ge1$, but then show that for any integer $k\ge1$, a best monotone theorem for $t=\frac1k\le 1$ requires at least $f(k)\cdot|V(G)|$ nonredundant conditions, where $f(k)$ grows superpolynomially as $k\rightarrow\infty$. When $t<1$, we give an additional, simple theorem for $G$ to be $t$-tough, in terms of its vertex degrees.