Article ID Journal Published Year Pages File Type
4651334 Discrete Mathematics 2006 8 Pages PDF
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
,