Toughness and hamiltonicity in image-trees Original Research Article

We consider toughness conditions that guarantee the existence of a hamiltonian cycle in image-trees, a subclass of the class of chordal graphs. By a result of Chen et al. 18-tough chordal graphs are hamiltonian, and by a result of Bauer et al. there exist nontraceable chordal graphs with toughness arbitrarily close to image. It is believed that the best possible value of the toughness guaranteeing hamiltonicity of chordal graphs is less than 18, but the proof of Chen et al. indicates that proving a better result could be very complicated. We show that every 1-tough 2-tree on at least three vertices is hamiltonian, a best possible result since 1-toughness is a necessary condition for hamiltonicity. We generalize the result to image-trees for image: Let image be a image-tree. If image has toughness at least image then image is hamiltonian. Moreover, we present infinite classes of nonhamiltonian 1-tough image-trees for each image.