Skip to Main content Skip to Navigation
Conference papers

On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1)

Abstract : 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.
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/hal-01215102
Contributor : Coordination Episciences Iam <>
Submitted on : Tuesday, October 13, 2015 - 3:06:49 PM
Last modification on : Monday, November 16, 2020 - 3:56:03 PM
Long-term archiving on: : Thursday, April 27, 2017 - 12:02:36 AM

File

dmAO0137.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01215102, version 1

Collections

Citation

Andrew Goodall, Criel Merino, Anna de Mier, Marc Noy. On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1). 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.411-422. ⟨hal-01215102⟩

Share

Metrics

Record views

372

Files downloads

685