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
Descripción
Sumario: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).