The number of maximum matchings in a tree

Details The number of maximum matchings in a tree The number of maximum matchings in a tree

2010-11-30

arxiv.org/abs/1011.6554v1

Mathematics

Combinatorics

38 pages

Scientific paper

10.1016/j.disc.2011.07.028

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

Affiliated with

Also associated with

No associations

Rating

The number of maximum matchings in a tree does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The number of maximum matchings in a tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The number of maximum matchings in a tree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-445385