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



Is the following invariant of rooted trees a complete invariant?
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.)


