Welcome to MathOverflow

Question

3

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?

flag	asked Apr 22 2010 at 14:07 Hans Stricker 5,233●12●38

1

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 2010 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 2010 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 2010 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 2010 at 11:05

Jeremy Martin · Answer 1 · 2010-08-18 21:51:31Z UTC

@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).

Complete tree invariants?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.