Geodesic
On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1)
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) (2011).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2011_special_260_a34,
     author = {Goodall, Andrew and Merino, Criel and de Mier, Anna and Noy, Marc},
     title = {On the evaluation of the {Tutte} polynomial at the points (1,-1) and (2,-1)},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)},
     year = {2011},
     doi = {10.46298/dmtcs.2921},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2921/}
}
TY  - JOUR
AU  - Goodall, Andrew
AU  - Merino, Criel
AU  - de Mier, Anna
AU  - Noy, Marc
TI  - On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1)
JO  - Discrete mathematics & theoretical computer science
PY  - 2011
VL  - DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2921/
DO  - 10.46298/dmtcs.2921
LA  - en
ID  - DMTCS_2011_special_260_a34
ER  - 
%0 Journal Article
%A Goodall, Andrew
%A Merino, Criel
%A de Mier, Anna
%A Noy, Marc
%T On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1)
%J Discrete mathematics & theoretical computer science
%D 2011
%V DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2921/
%R 10.46298/dmtcs.2921
%G en
%F DMTCS_2011_special_260_a34
Goodall, Andrew; Merino, Criel; de Mier, Anna; Noy, Marc. On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1). Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) (2011). doi : 10.46298/dmtcs.2921. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2921/

Cité par Sources :