A graph G is t-tough if any induced subgraph of it with x > 1 connected components is obtained from G by deleting at least tx vertices. It is shown that for every t and g there are t-tough graphs of girth strictly greater than g. This strengthens a recent result of Bauer, van den Heuvel and Schmeichel who proved the above for g = 3, and hence disproves in a strong sense a conjecture of Chvátal that there exists an absolute constant t0 so that every t0-tough graph is pancyclic. The proof is by an explicit construction based on the tight relationship between the spectral properties of a regular graph and its expansion properties. A similar technique provides a simple construction of triangle-free graphs with independence number m on Ω(m4/3) vertices, improving previously known explicit constructions by Erdös and by Chung, Cleve and Dagum.
|Original language||English (US)|
|Number of pages||7|
|Journal||Journal of Algebraic Combinatorics: An International Journal|
|State||Published - Jan 1 1995|
All Science Journal Classification (ASJC) codes
- Algebra and Number Theory
- Discrete Mathematics and Combinatorics