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

Résumé : C. Merino [Electron. J. Combin. 15 (2008)] a montré que le polynôme de Tutte du graphe complet satisfait $t(K_{n+2};2,-1)=t(K_n;1,-1)$. Le rapport entre le polynôme de Tutte et le polynôme d'inversions d'un arbre nous permet de donner une preuve bijective de cette identité. Le résultat principal du travail est une condition suffisante pour qu'un graphe ait deux sommets u et v tels que $t(G;2,-1)=t(G-\{u,v\};1,-1)$; en particulier, les graphes ``threshold'' satisfont cette condition. Finalement, nous donnons une formule pour $t(K_{n,m};2,-1)$ qui fait intervenir les permutations alternées.
Type de document :
Communication dans un congrès
Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), pp.411-422, 2011, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01215102
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 13 octobre 2015 - 15:06:49
Dernière modification le : mardi 7 mars 2017 - 15:13:03
Document(s) archivé(s) le : jeudi 27 avril 2017 - 00:02:36

Fichier

dmAO0137.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • 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). Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), pp.411-422, 2011, DMTCS Proceedings. 〈hal-01215102〉

Partager

Métriques

Consultations de la notice

166

Téléchargements de fichiers

153