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?

Improve this question
$\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
    Commented 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
    Commented 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$
    – Hans-Peter Stricker
    Commented 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$
    – Hans-Peter Stricker
    Commented Apr 23, 2010 at 11:05

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .