Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651473 | Discrete Mathematics | 2006 | 4 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
David Eisenstat, Gary Gordon,