کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651473 | 1632451 | 2006 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Non-isomorphic caterpillars with identical subtree data
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The greedoid Tutte polynomial of a tree is equivalent to a generating function that encodes information about the number of subtrees with I internal (non-leaf) edges and L leaf edges, for all I and L. We prove that this information does not uniquely determine the tree T by constructing an infinite family of pairs of non-isomorphic caterpillars, each pair having identical subtree data. This disproves conjectures of [S. Chaudhary, G. Gordon, Tutte polynomials for trees, J. Graph Theory 15 (1991) 317-331] and [G. Gordon, E. McDonnell, D. Orloff, N. Yung, On the Tutte polynomial of a tree, Congr. Numer. 108 (1995) 141-151] and contrasts with the situation for rooted trees, where this data completely determines the rooted tree.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issues 8â9, 1 May 2006, Pages 827-830
Journal: Discrete Mathematics - Volume 306, Issues 8â9, 1 May 2006, Pages 827-830
نویسندگان
David Eisenstat, Gary Gordon,