کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651143 1632447 2007 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Toughness and hamiltonicity in kk-trees
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Toughness and hamiltonicity in kk-trees
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issues 7–8, 6 April 2007, Pages 832–838
نویسندگان
, , ,