Skip to main content
actual answer!
Source Link
Jeremy Martin
  • 1.5k
  • 10
  • 16

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

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.

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

Source Link
Jeremy Martin
  • 1.5k
  • 10
  • 16

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.