MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
In case this may be of interested, a conjectural complete tree invariant is the chromatic symmetric function:… – 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).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.