Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651334 | Discrete Mathematics | 2006 | 8 Pages |
Abstract
The toughness of a graph G is defined as the largest real number t such that deletion of any s points from G results in a graph which is either connected or else has at most s/ts/t components. Clearly, every hamiltonian graph is 1-tough. Conversely, we conjecture that for some t0t0, every t0t0-tough graph is hamiltonian. Since a square of a k-connected graph is always k -tough, a proof of this conjecture with t0=2t0=2 would imply Fleischner's theorem (the square of a block is hamiltonian). We construct an infinite family of (3/2)-tough nonhamiltonian graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
V. Chvátal,