Title of article :
Non-isomorphic caterpillars with identical subtree data
Author/Authors :
David Eisenstat، نويسنده , , Gary Gordon and Elizabeth McMahon، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2006
Abstract :
The greedoid Tutte polynomial of a tree is equivalent to a generating function that encodes information about the number of subtrees with image internal (non-leaf) edges and image 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 and contrasts with the situation for rooted trees, where this data completely determines the rooted tree.
Keywords :
Tree , Subtree , Greedoid Tutte polynomial
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics