Article ID Journal Published Year Pages File Type
4651143 Discrete Mathematics 2007 7 Pages PDF
Abstract

We consider toughness conditions that guarantee the existence of a hamiltonian cycle in kk-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 74. 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 kk-trees for k⩾2k⩾2: Let GG be a kk-tree. If GG has toughness at least (k+1)/3,(k+1)/3, then GG is hamiltonian. Moreover, we present infinite classes of nonhamiltonian 1-tough kk-trees for each k⩾3k⩾3.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,