Toughness and binding number

D. Bauer, N. Kahl, E. Schmeichel, D. R. Woodall, M. Yatauro

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


Let τ(G) and bind(G) be the toughness and binding number, respectively, of a graph G. Woodall observed in 1973 that τ(G)≥bind(G)-1. In this paper, we obtain best possible improvements of this inequality except when (1+5)/2<bind(G)<2 and bind(G) has even denominator when expressed in lowest terms.

Original languageEnglish (US)
Pages (from-to)60-68
Number of pages9
JournalDiscrete Applied Mathematics
StatePublished - Mar 11 2014

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


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

Cite this