Toughness and hamiltonicity in kk-trees Export

@article{citeulike:5090940, abstract = {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 inlMMLBox . 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 k 2 : 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 k 3 .}, author = {Broersma, H. and Xiong, L. and Yoshimoto, K.}, citeulike-article-id = {5090940}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.disc.2005.11.051}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0012365X06005759}, day = {06}, doi = {10.1016/j.disc.2005.11.051}, issn = {0012365X}, journal = {Discrete Mathematics}, keywords = {graph, hamiltonian}, month = {April}, number = {7-8}, pages = {832--838}, posted-at = {2009-07-08 04:58:22}, priority = {2}, title = {Toughness and hamiltonicity in kk-trees}, url = {http://dx.doi.org/10.1016/j.disc.2005.11.051}, volume = {307}, year = {2007} }

TY - JOUR ID - citeulike:5090940 L3 - citeulike-article-id:5090940 N2 - 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 inlMMLBox . 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 k 2 : 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 k 3 . IS - 7-8 JF - Discrete Mathematics SN - 0012365X EP - 838 TI - Toughness and hamiltonicity in kk-trees VL - 307 SP - 832 KW - graph KW - hamiltonian AU - Broersma, H AU - Xiong, L AU - Yoshimoto, K PY - 2007/04/06/ UR - http://dx.doi.org/10.1016/j.disc.2005.11.051 ER -