most recent 30 from http://mathoverflow.net 2013-06-20T02:18:12Z http://mathoverflow.net/feeds/question/22185 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/22185/complete-tree-invariants Hans Stricker 2010-04-22T14:07:32Z 2010-08-18T21:51:31Z

<p>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 <a href="http://en.wikipedia.org/wiki/Graph_invariant" rel="nofollow">Wikipedia</a>), I have the feeling that Harrsion's question for <a href="http://mathoverflow.net/questions/11631/complete-graph-invariants" rel="nofollow">complete graph invariants</a> remained basically unanswered, since <a href="http://mathoverflow.net/questions/11631/complete-graph-invariants/11715#11715" rel="nofollow">Greg's answer</a> is mainly about (canonical) labellings. </p> <p>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:</p> <blockquote> <p>Are there any known complete tree invariants?</p> </blockquote>

http://mathoverflow.net/questions/22185/complete-tree-invariants/36029#36029 Jeremy Martin 2010-08-18T21:51:31Z 2010-08-18T21:51:31Z

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