## Abstract

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 t_{0} so that every t_{0}-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 Ω(m^{4/3}) vertices, improving previously known explicit constructions by Erdös and by Chung, Cleve and Dagum.

Original language | English (US) |
---|---|

Pages (from-to) | 189-195 |

Number of pages | 7 |

Journal | Journal of Algebraic Combinatorics: An International Journal |

Volume | 4 |

Issue number | 3 |

DOIs | |

State | Published - Jan 1 1995 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Algebra and Number Theory
- Discrete Mathematics and Combinatorics