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).
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 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

Identifiers

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

Share

Metrics

Record views

223

Files downloads

480