Toughness and vertex degrees

D. Bauer, Haitze J. Broersma, J. van den Heuvel, N. Kahl, E. Schmeichel

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)


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 languageEnglish
Pages (from-to)209-219
Number of pages11
JournalJournal of graph theory
Issue number2
Publication statusPublished - 2013


  • MSC-05C
  • Toughness
  • EWI-23370
  • IR-86131
  • Degree condition
  • METIS-297654
  • Best monotone theorem


Dive into the research topics of 'Toughness and vertex degrees'. Together they form a unique fingerprint.

Cite this