pith. sign in

arxiv: 1011.6554 · v1 · pith:RPISH2GCnew · submitted 2010-11-30 · 🧮 math.CO

The number of maximum matchings in a tree

classification 🧮 math.CO
keywords matchingsnumbermaximumtreetreeslowermaximalorder
0
0 comments X
read the original abstract

We determine upper and lower bounds for the number of maximum matchings (i.e., matchings of maximum cardinality) $m(T)$ of a tree $T$ of given order. While the trees that attain the lower bound are easily characterised, the trees with 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 $O(1.391664^n)$ (the precise constant being an algebraic number of degree 14). As a corollary, we improve on a recent result by G\'orska and Skupie\'n on the number of maximal matchings (maximal with respect to set inclusion).

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.