The number of maximum matchings in a tree

Simple item page
dc.contributor.authorHeuberger C.
dc.contributor.authorWagner S.
dc.date.accessioned2011-10-13T16:59:37Z
dc.date.available2011-10-13T16:59:37Z
dc.date.issued2011
dc.description.abstractWe 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.
dc.description.versionArticle
dc.identifier.citationDiscrete Mathematics
dc.identifier.citation311
dc.identifier.citation21
dc.identifier.citationhttp://www.scopus.com/inward/record.url?eid=2-s2.0-80052596761&partnerID=40&md5=431e2477dcaa3b98ec0481cd59deaa89
dc.identifier.issn0012365X
dc.identifier.other10.1016/j.disc.2011.07.028
dc.identifier.urihttp://hdl.handle.net/10019.1/17179
dc.titleThe number of maximum matchings in a tree
dc.typeArticle
Files
Collections
Stellenbosch University - Scopus Publications