The number of 0-1-2 increasing trees as two different evaluations of the Tutte polynomial of a complete graph

C. Merino

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

If $T_{n}(x,y)$ is the Tutte polynomial of the complete graph $K_n$, we have the equality $T_{n+1}(1,0)=T_{n}(2,0)$. This has an almost trivial proof with the right combinatorial interpretation of $T_{n}(1,0)$ and $T_{n}(2,0)$. We present an algebraic proof of a result with the same flavour as the latter: $T_{n+2}(1,-1)=T_n(2,-1)$, where $T_{n}(1,-1)$ has the combinatorial interpretation of being the number of 0–1–2 increasing trees on $n$ vertices.

Détail

DOI : 10.37236/903

Classification : 05A19