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-iD1; Criel Merino ORCID-iD2; Anna de Mier 3; Marc Noy 3

  • 1 Department of Applied Mathematics and Institute of Theoretical Computer Science
  • 2 Instituto de Matematicas
  • 3 Universitat Politècnica de Catalunya [Barcelona]

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]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1016/0097-3165(79)90108-0
  • 10.1016/0097-3165(79)90108-0
Depth-first search as a combinatorial correspondence

Consultation statistics

This page has been seen 165 times.
This article's PDF has been downloaded 184 times.