Recall that rooted trees may be generated by starting with a trivial rooted tree (just a vertex), along with the operations of grafting a number of trees (identify their roots) and adding a new vertex to the tree to be a new minimum element. We will call this second operation "leafing".
Now let us define an invariant of rooted trees. If $T$ is a rooted tree, we will denote $P_T(z)$ to be the associated polynomial.
If the number of edges of $T$ is zero, then $P_T(z)=1$.
If $T'$ is the leafing of $T$, then $P_{T'}(z)=(z+1)P(z)+1$.
If $T$ is the grafting of $T_i, i=1\ldots n$, then $P_T(z)=P_{T_1}(z)P_{T_2}(z)\ldots P_{T_n}(z)$.
This polynomial is an isomorphism invariant of rooted trees. My question is
If $P_T=P_{T'}$, are the rooted trees, $T,T"$ isomorphic? If these trees are not isomorphic, what is the smallest counterexample? Any references to this invariant would be appreciated.
Best Answer
Chaudhary and Gordon ("Tutte polynomials for trees," J. Graph Theory 15, no. 3 (1991), 317-331) construct a couple of invariants that look very similar to yours. They prove that these invariants do in fact determine a rooted tree up to isomorphism.
Update: I think the answer to your original question is no.
The relevant invariant from the Chaudhary-Gordon paper is what they call $f_p(T;t,z)$. This is a polynomial in two variables $t,z$ that satisfies the recurrence $$ f_p(L(T);t,z) = t(z+1)f(T) + 1 - tz,$$ $$ f_p(T_1*\cdots*T_r;t,z) = f(T_1)\cdots f(T_r)$$
where $L$ means leafing and $*$ means grafting. (These are Prop 4(b) and and Prop 5 in Chaudhary-Gordon.) If I'm doing the algebra right, your invariant is $P_T(z) = f_p(T;z+1,0).$
Chaudhary and Gordon give an example of two rooted trees on 8 vertices with the same values of $f_p(T;t,z)$. The edge sets could be labeled as 01,12,24,13,35,56,57 and 01,12,13,34,35,56,67, with 0 the root vertex in both cases. (Probably a good idea to confirm this if you have code to compute your invariant quickly.)