title: The number of maximum matchings in a tree.
abstract: We determine upper and lower bounds for the number of maximum matchings (i.e., matchings of maximum cardinality) [Formula: see text] of a tree T 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 n 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).
authors.affiliation: Institut für Mathematik B, Technische Universität Graz, Austria.
authors.forename: Clemens
authors.initials: C
authors.lastname: Heuberger
authors.forename: Stephan
authors.initials: S
authors.lastname: Wagner