Title:
Not every 2-tough graph is Hamiltonian
Author(s):
D. Bauer, H.J. Broersma & H.J. Veldman
Abstract:
We present 
-tough graphs without a Hamilton
path for arbitrary 
, thereby refuting a well-known
conjecture due to Chvátal. We also present 
-tough chordal graphs without a Hamilton path
for any 
.
Keywords:
Hamiltonian graph, traceable graph,
toughness, 2-tough graph, chordal graph
Mathematics Subject Classification:
05C45, 05C38, 05C35