# Complete tree invariants?

If we take a graph invariant to be "a property that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph" (from Wikipedia), I have the feeling that Harrsion's question for complete graph invariants remained basically unanswered, since Greg's answer is mainly about (canonical) labellings.

Thinking - as Harrison did - of "the usual ones (the Tutte polynomial, the spectrum, whatever)", I'd like to repeat Harrison's question, but restrict it to trees:

Are there any known complete tree invariants?

-
In case this may be of interested, a conjectural complete tree invariant is the chromatic symmetric function: garden.irmacs.sfu.ca/?q=op/… – Steven Sam Apr 22 '10 at 14:38
All trees on $n$ vertices have the same Tutte polynomial, so it's not that. Are you just asking for a canonical labelling? – Emil Apr 22 '10 at 21:52
@Emil: No, I am not asking for a canonical labelling, but for something more "structural", something expressible without any usage of labels. – Hans Stricker Apr 23 '10 at 6:10
@Steven: Can you - or someone else - tell me, what the "path sequence" is? (I didn't find a definition with Google.) Thanks! – Hans Stricker Apr 23 '10 at 11:05

@Hans: The path sequence of $G$ is $(p_1, p_2, ...)$ where $p_i$ is the number of $i$-edge path subgraphs of $G$ isomorphic to an $i$-edge path. For a tree, this is the same as the number of pairs of vertices at mutual distance $i$. Morin, Wagner and I proved [arXiv:math/0609339] that the path and degree sequences of a tree (actually, something a but more general) can be determined from its chromatic symmetric function, but OTOH the path and degree sequences do not together determine the tree up to isomorphism; there is an 11-vertex counterexample in our article (due to Eisenstat and Gordon).