Cargando…
The number of maximum matchings in a tree
We determine upper and lower bounds for the number of maximum matchings (i.e., matchings of maximum cardinality) [Formula: see text] of a tree [Formula: see text] of given order. While the trees that attain the lower bound are easily characterised, the trees with the largest number of maximum matchi...
Autores principales: | , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Elsevier
2011
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3226351/ https://www.ncbi.nlm.nih.gov/pubmed/22158732 http://dx.doi.org/10.1016/j.disc.2011.07.028 |
_version_ | 1782217605745999872 |
---|---|
author | Heuberger, Clemens Wagner, Stephan |
author_facet | Heuberger, Clemens Wagner, Stephan |
author_sort | Heuberger, Clemens |
collection | PubMed |
description | We determine upper and lower bounds for the number of maximum matchings (i.e., matchings of maximum cardinality) [Formula: see text] of a tree [Formula: see text] of given order. While the trees that attain the lower bound are easily characterised, the trees with the largest number of maximum matchings show a very subtle structure. We give a complete characterisation of these trees and derive that the number of maximum matchings in a tree of order [Formula: see text] is at most [Formula: see text] (the precise constant being an algebraic number of degree 14). As a corollary, we improve on a recent result by Górska and Skupień on the number of maximal matchings (maximal with respect to set inclusion). |
format | Online Article Text |
id | pubmed-3226351 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2011 |
publisher | Elsevier |
record_format | MEDLINE/PubMed |
spelling | pubmed-32263512011-12-05 The number of maximum matchings in a tree Heuberger, Clemens Wagner, Stephan Discrete Math Article We determine upper and lower bounds for the number of maximum matchings (i.e., matchings of maximum cardinality) [Formula: see text] of a tree [Formula: see text] of given order. While the trees that attain the lower bound are easily characterised, the trees with the largest number of maximum matchings show a very subtle structure. We give a complete characterisation of these trees and derive that the number of maximum matchings in a tree of order [Formula: see text] is at most [Formula: see text] (the precise constant being an algebraic number of degree 14). As a corollary, we improve on a recent result by Górska and Skupień on the number of maximal matchings (maximal with respect to set inclusion). Elsevier 2011-11-06 /pmc/articles/PMC3226351/ /pubmed/22158732 http://dx.doi.org/10.1016/j.disc.2011.07.028 Text en © 2011 Elsevier B.V. https://creativecommons.org/licenses/by-nc-nd/3.0/ Open Access under CC BY-NC-ND 3.0 (https://creativecommons.org/licenses/by-nc-nd/3.0/) license |
spellingShingle | Article Heuberger, Clemens Wagner, Stephan The number of maximum matchings in a tree |
title | The number of maximum matchings in a tree |
title_full | The number of maximum matchings in a tree |
title_fullStr | The number of maximum matchings in a tree |
title_full_unstemmed | The number of maximum matchings in a tree |
title_short | The number of maximum matchings in a tree |
title_sort | number of maximum matchings in a tree |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3226351/ https://www.ncbi.nlm.nih.gov/pubmed/22158732 http://dx.doi.org/10.1016/j.disc.2011.07.028 |
work_keys_str_mv | AT heubergerclemens thenumberofmaximummatchingsinatree AT wagnerstephan thenumberofmaximummatchingsinatree AT heubergerclemens numberofmaximummatchingsinatree AT wagnerstephan numberofmaximummatchingsinatree |