On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1)
International audience 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 tre...
Published in: | Discrete Mathematics & Theoretical Computer Science |
---|---|
Main Authors: | , , , |
Other Authors: | , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2011
|
Subjects: | |
Online Access: | https://hal.inria.fr/hal-01215102 https://hal.inria.fr/hal-01215102/document https://hal.inria.fr/hal-01215102/file/dmAO0137.pdf https://doi.org/10.46298/dmtcs.2921 |
id |
ftunivnantes:oai:HAL:hal-01215102v1 |
---|---|
record_format |
openpolar |
spelling |
ftunivnantes:oai:HAL:hal-01215102v1 2023-05-15T16:51:27+02:00 On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1) Goodall, Andrew Merino, Criel de Mier, Anna Noy, Marc Department of Applied Mathematics and Institute of Theoretical Computer Science (Charles University) Charles University Prague (CU) Instituto de Matematicas (UNAM) Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM) Universitat Politècnica de Catalunya Barcelona (UPC) Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel Reykjavik, Iceland 2011 https://hal.inria.fr/hal-01215102 https://hal.inria.fr/hal-01215102/document https://hal.inria.fr/hal-01215102/file/dmAO0137.pdf https://doi.org/10.46298/dmtcs.2921 en eng HAL CCSD Discrete Mathematics and Theoretical Computer Science DMTCS info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2921 hal-01215102 https://hal.inria.fr/hal-01215102 https://hal.inria.fr/hal-01215102/document https://hal.inria.fr/hal-01215102/file/dmAO0137.pdf doi:10.46298/dmtcs.2921 info:eu-repo/semantics/OpenAccess ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://hal.inria.fr/hal-01215102 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.411-422, ⟨10.46298/dmtcs.2921⟩ Tutte polynomial increasing tree threshold graph generating function up-down permutation [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] info:eu-repo/semantics/conferenceObject Conference papers 2011 ftunivnantes https://doi.org/10.46298/dmtcs.2921 2022-08-10T07:41:59Z International audience 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. 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. Conference Object Iceland Université de Nantes: HAL-UNIV-NANTES Discrete Mathematics & Theoretical Computer Science DMTCS Proceeding Proceedings |
institution |
Open Polar |
collection |
Université de Nantes: HAL-UNIV-NANTES |
op_collection_id |
ftunivnantes |
language |
English |
topic |
Tutte polynomial increasing tree threshold graph generating function up-down permutation [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
spellingShingle |
Tutte polynomial increasing tree threshold graph generating function up-down permutation [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Goodall, Andrew Merino, Criel de Mier, Anna Noy, Marc On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1) |
topic_facet |
Tutte polynomial increasing tree threshold graph generating function up-down permutation [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
description |
International audience 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. 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. |
author2 |
Department of Applied Mathematics and Institute of Theoretical Computer Science (Charles University) Charles University Prague (CU) Instituto de Matematicas (UNAM) Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM) Universitat Politècnica de Catalunya Barcelona (UPC) Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel |
format |
Conference Object |
author |
Goodall, Andrew Merino, Criel de Mier, Anna Noy, Marc |
author_facet |
Goodall, Andrew Merino, Criel de Mier, Anna Noy, Marc |
author_sort |
Goodall, Andrew |
title |
On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1) |
title_short |
On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1) |
title_full |
On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1) |
title_fullStr |
On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1) |
title_full_unstemmed |
On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1) |
title_sort |
on the evaluation of the tutte polynomial at the points (1,-1) and (2,-1) |
publisher |
HAL CCSD |
publishDate |
2011 |
url |
https://hal.inria.fr/hal-01215102 https://hal.inria.fr/hal-01215102/document https://hal.inria.fr/hal-01215102/file/dmAO0137.pdf https://doi.org/10.46298/dmtcs.2921 |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://hal.inria.fr/hal-01215102 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.411-422, ⟨10.46298/dmtcs.2921⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2921 hal-01215102 https://hal.inria.fr/hal-01215102 https://hal.inria.fr/hal-01215102/document https://hal.inria.fr/hal-01215102/file/dmAO0137.pdf doi:10.46298/dmtcs.2921 |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.46298/dmtcs.2921 |
container_title |
Discrete Mathematics & Theoretical Computer Science |
container_volume |
DMTCS Proceeding |
container_issue |
Proceedings |
_version_ |
1766041566008311808 |