Discrete Mathematics & Theoretical Computer Science |

2921

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.

Source : oai:HAL:hal-01215102v1

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]

This page has been seen 149 times.

This article's PDF has been downloaded 170 times.