The number of maximum matchings in a tree

DOI10.1016/J.DISC.2011.07.028MaRDI QIDQ409365zbMATH OpenOpenAlexWikidataFDO

Authors Clemens Heuberger, Stephan Wagner

Publication date 13 April 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1011.6554

zbMATH Keywords

treesboundsmaximum matchingsstructural characterisation

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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

Recommendations

• Trees with maximum number of maximal matchings
• On the number of matchings of a tree
• The maximum number of spanning trees of a graph with given matching number
• Generalized matchings in trees
• The lower bound on the number of maximum matchings of a graph

Cites work

• scientific article; zbMATH DE number 1618184 (Why is no real title available?)
• scientific article; zbMATH DE number 4074878 (Why is no real title available?)
• scientific article; zbMATH DE number 3720958 (Why is no real title available?)
• scientific article; zbMATH DE number 3745213 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 808335 (Why is no real title available?)
• A Note on Independent Sets in Trees
• Binary trees with the largest number of subtrees
• Largest Number of Subtrees of Trees with a Given Maximum Degree
• Matching theory
• Maxima and minima of the Hosoya index and the Merrifield-Simmons index
• Recurrence among trees with most numerous efficient dominating sets
• The Number of Maximal Independent Sets in a Tree
• The number of maximum matchings in a tree
• Theory of monomer-dimer systems
• Trees with extremal numbers of dominating sets
• Trees with maximum number of maximal matchings
• Two Notes on Notation

Cited in

(22)

• Maximal independent sets and maximal matchings in series-parallel and related graph classes
• Generalized matchings in trees
• scientific article; zbMATH DE number 140121 (Why is no real title available?)
• On the number of \(F\)-matchings in a tree
• Alternating Whitney sums and matchings in trees. II
• Null decomposition of trees
• On the number of matchings of a tree
• The Maximum Binary Tree Problem.
• On radius 2 trees with the maximum number of matchings
• The number of maximum matchings in a tree
• Maximal outer planar graph and perfect matching in treelike triangular lattices and treelike polyominoes
• Trees with minimum number of infima closed sets
• scientific article; zbMATH DE number 3983182 (Why is no real title available?)
• Trees with maximum number of maximal matchings
• On trees with a maximum proper partial 0-1 coloring containing a maximum matching
• The total number of matchings of \(L_{n,p}^*\)
• The maximum number of spanning trees of a graph with given matching number
• On the number of \(r\)-matchings in a tree
• Matchings in starlike trees
• Number of pairs of template matchings in \(q\)-ary tree with randomly marked vertices
• scientific article; zbMATH DE number 434499 (Why is no real title available?)
• Maximal independent sets and maximal matchings in series-parallel and related graph classes

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: The number of maximum matchings in a tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q409365)