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)

Authors: Andrew Goodall ORCID-iD; Criel Merino ORCID-iD; Anna de Mier ; Marc Noy

    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]

    Share

    Consultation statistics

    This page has been seen 149 times.
    This article's PDF has been downloaded 170 times.