Connection between the Tutte and characteristic polynomials?

392 Views Asked by At

Both the Tutte polynomial $T_G(x,y)$ and the characteristic polynomial $\phi_G(x)$ encode a great amount of structure of the input graph $G$. I've read somewhere that the Tutte polynomial has a kind of universality property,

... any graph invariant that is multiplicative on disjoint unions and one point joins and has a deletion/contraction reduction must be an evaluation of the Tutte polynomial.

The characteristic polynomial is multiplicative on disjoint unions but I don't think there is a deletion/contraction reduction. Furthermore, I think there are isomorphically distinct graphs $A,B$ such that $T_A = T_B$ but $\phi_A \neq \phi_B$ and conversely there are graphs $C,D$ such that $\phi_C = \phi_D$ but $T_C \neq T_D$. If this is true then they must encode different information on some level.

Question: What connection (if any) is there between the two graph polynomials?

1

There are 1 best solutions below

2
On

All trees on $n$ vertices have the same Tutte polynomial, but their characteristic polynomials vary extensively. On the other hand there are cospectral graphs which have different chromatic number, and therefore have different Tutte polynomial. So there is no obvious way of transferring information from one polynomial to the other.