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...

Descripción completa

Detalles Bibliográficos
Autores principales: Heuberger, Clemens, Wagner, Stephan
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