How to contact me.
[Un]solved problem 21, from Bondy and Murty's list.
and H.J. Veldmanb.
Not every 2-tough graph is Hamiltonian.
Discrete Applied Mathematics 99(2000), 317-321.
© 2000 Elsevier Science B.V. All rights reserved.
aDepartment of Mathematical Sciences, Stevens Institute of
Technology, Hoboken, NJ 07030, USA
bFaculty of Mathematical Sciences, University of Twente, P.O. Box
217, 7500 AE Enschede, The Netherlands
Received 19 June 1997; received in revised form 27 January 1998;
accepted 9 March 1999
The first two authors dedicate this paper to the memory of their dear
friend and coauthor Henk Tau Veldman, who died October 12, 1998.
We present (9/4 - e)-tough graphs without a Hamilton path for arbitrary
e>0, thereby refuting a well-known conjecture due to Chvátal. We also
present (7/4 - e)-tough chordal graphs without a Hamilton path for any
MSC: 05C45; 05C38; 05C35
Keywords: Hamiltonian graph; Traceable graph; Toughness; 2-tough graph;
Last modified April 30, 2000, by S.C. Locke.