7
$\begingroup$

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?

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

1 Answer 1

7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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