The number of maximum matchings in a tree

DOI10.1016/J.DISC.2011.07.028zbMATH Open1238.05146arXiv1011.6554OpenAlexW2147992535WikidataQ35579446 ScholiaQ35579446MaRDI QIDQ409365FDOQ409365

Authors: Clemens Heuberger, Stephan Wagner 

Publication date: 13 April 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

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

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

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

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)

Cites Work

• Matching theory
• Theory of monomer-dimer systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Trees with extremal numbers of dominating sets
• Title not available (Why is that?)
• Largest Number of Subtrees of Trees with a Given Maximum Degree
• Title not available (Why is that?)
• Maxima and minima of the Hosoya index and the Merrifield-Simmons index
• Two Notes on Notation
• Binary trees with the largest number of subtrees
• Title not available (Why is that?)
• The Number of Maximal Independent Sets in a Tree
• A Note on Independent Sets in Trees
• Title not available (Why is that?)
• The number of maximum matchings in a tree
• Title not available (Why is that?)
• Recurrence among trees with most numerous efficient dominating sets
• Trees with maximum number of maximal matchings

Cited In (22)

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

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)