Toughness Counterexample

How to contact me.

[Un]solved problem 21, from Bondy and Murty's list.

D. Bauer^a, H.J. Broersma^b, and H.J. Veldman^b. Not every 2-tough graph is Hamiltonian. Discrete Applied Mathematics 99(2000), 317-321. Š 2000 Elsevier Science B.V. All rights reserved. PII: S0166-218X(99)00141-9

^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.

Abstract

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 e>0.

MSC: 05C45; 05C38; 05C35

Keywords: Hamiltonian graph; Traceable graph; Toughness; 2-tough graph; Chordal graph

Last modified April 30, 2000, by S.C. Locke.