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
Fingerprint
Dive into the research topics of 'Toughness and vertex degrees'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver