Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).

# 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.
Keywords :
Document type :
Conference papers
Domain :
Complete list of metadata

Cited literature [7 references]

https://hal.inria.fr/hal-01215102
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Tuesday, October 13, 2015 - 3:06:49 PM
Last modification on : Wednesday, November 10, 2021 - 5:38:03 PM
Long-term archiving on: : Thursday, April 27, 2017 - 12:02:36 AM

### File

dmAO0137.pdf
Publisher files allowed on an open archive

### 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, ⟨10.46298/dmtcs.2921⟩. ⟨hal-01215102⟩

Record views