The number of maximum matchings in a tree
Date
2011
Authors
Heuberger C.
Wagner S.
Journal Title
Journal ISSN
Volume Title
Publisher
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 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 O(1.391664n) (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). © 2011 Elsevier B.V. All rights reserved.
Description
Keywords
Citation
Discrete Mathematics
311
21
http://www.scopus.com/inward/record.url?eid=2-s2.0-80052596761&partnerID=40&md5=431e2477dcaa3b98ec0481cd59deaa89
311
21
http://www.scopus.com/inward/record.url?eid=2-s2.0-80052596761&partnerID=40&md5=431e2477dcaa3b98ec0481cd59deaa89