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 is at least 1, but then show that for any integer k > 0, a best monotone theorem for t=1/k requires at least f(k)|V(G)| nonredundant conditions, where f(k) grows superpolynomially as k grows to infinity. When t < 1, we give an additional, simple theorem for G to be t-tough, in terms of its vertex degrees.
Original language | English |
---|---|
Pages (from-to) | 209-219 |
Number of pages | 11 |
Journal | Journal of graph theory |
Volume | 72 |
Issue number | 2 |
DOIs | |
Publication status | Published - 2013 |
Keywords
- MSC-05C
- Toughness
- EWI-23370
- IR-86131
- Degree condition
- METIS-297654
- Best monotone theorem