Andrew Goodall ; Criel Merino ; Anna de Mier ; Marc Noy - On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1)

dmtcs:2921 - Discrete Mathematics & Theoretical Computer Science, January 1, 2011, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) - https://doi.org/10.46298/dmtcs.2921
On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1)Article

Authors: Andrew Goodall ORCID1; Criel Merino ORCID2; Anna de Mier ORCID3,4; Marc Noy 3,4

C. Merino [Electron. J. Combin. 15 (2008)] showed that the Tutte polynomial of a complete graph satisfies $t(K_{n+2};2,-1)=t(K_n;1,-1)$. We first give a bijective proof of this identity based on the relationship between the Tutte polynomial and the inversion polynomial for trees. Next we move to our main result, a sufficient condition for a graph G to have two vertices u and v such that $t(G;2,-1)=t(G-\{u,v\};1,-1)$; the condition is satisfied in particular by the class of threshold graphs. Finally, we give a formula for the evaluation of $t(K_{n,m};2,-1)$ involving up-down permutations.


Volume: DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
Section: Proceedings
Published on: January 1, 2011
Imported on: January 31, 2017
Keywords: generating function,up-down permutation,Tutte polynomial,increasing tree,threshold graph,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 258 times.
This article's PDF has been downloaded 279 times.