### Abstract

Original language | Undefined |
---|---|

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

### Cite this

*Journal of graph theory*,

*72*(2), 209-219. https://doi.org/10.1002/jgt.21639

}

*Journal of graph theory*, vol. 72, no. 2, pp. 209-219. https://doi.org/10.1002/jgt.21639

**Toughness and vertex degrees.** / Bauer, D.; Broersma, Haitze J.; van den Heuvel, J.; Kahl, N.; Schmeichel, E.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - Toughness and vertex degrees

AU - Bauer, D.

AU - Broersma, Haitze J.

AU - van den Heuvel, J.

AU - Kahl, N.

AU - Schmeichel, E.

N1 - eemcs-eprint-23370

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - MSC-05C

KW - Toughness

KW - EWI-23370

KW - IR-86131

KW - Degree condition

KW - METIS-297654

KW - Best monotone theorem

U2 - 10.1002/jgt.21639

DO - 10.1002/jgt.21639

M3 - Article

VL - 72

SP - 209

EP - 219

JO - Journal of graph theory

JF - Journal of graph theory

SN - 0364-9024

IS - 2

ER -