Toughness and hamiltonicity in k -trees
- 作者：Hajo Broersma ; Liming Xiong ; Kiyoshi Yoshimoto
- 关键词：Toughness ; none ; color ; black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KY88S2-4&_mathId=mml13&_user=10&_cdi=5632&_rdoc=8&_acct=C000050221&_version=1&_userid=10&md5=3a0ef3e78fd7497bc73b66b596facc40"
- 刊名：Discrete Mathematics
- 出版年：2007
- 期刊代码：47_0012365x
- 类别：cp
- 出版时间：6 April 2007
- 卷：307
- 期：7-8
- 页码：832-838
- 文件大小：174 K
摘要
We consider toughness conditions that guarantee the existence of a hamiltonian cycle in k-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 . 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 k-trees for k2: Let G be a k-tree. If G has toughness at least (k+1)/3, then G is hamiltonian. Moreover, we present infinite classes of nonhamiltonian 1-tough k-trees for each k3.