Lesniak Abstract

Next: Latka Abstract Up: Index of Abstracts Previous: Sundaram Abstract

Tough Graph Theory
Linda Lesniak, Drew University




In 1973 Chvatal defined a noncomplete graph G to be 1-tough if for every cutset S of G, the number of components of G-S is at most |S|/t. In the same paper, Chvatal made an intriguing conjecture.

Conjecture: There exists t_0 such that every t_0-tough graph on at least three vertices is hamiltonian.

It has been shown that if this conjecture is true, then t_0 >=2. Direct progress on this "2-tough" conjecture has been minimal. However, this conjecture is closely related to several well-known theorems and conjectures and equivalent to yet others. Some recent results of this "family" of theorems and conjectures will be discussed.