Abstract
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 language | English (US) |
---|---|
Pages (from-to) | 60-68 |
Number of pages | 9 |
Journal | Discrete Applied Mathematics |
Volume | 165 |
DOIs | |
State | Published - Mar 11 2014 |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Applied Mathematics