کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651473 1632451 2006 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Non-isomorphic caterpillars with identical subtree data
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Non-isomorphic caterpillars with identical subtree data
چکیده انگلیسی
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
نویسندگان
, ,