On a constructive characterization of a class of trees related to pairs of disjoint matchings

Abstract

For a graph consider the pairs of disjoint matchings which union contains as many edges as possible, and define a parameter $\alpha$ which eqauls the cardinality of the largest matching in those pairs. Also, define $\betta$ to be the cardinality of a maximum matching of the graph. We give a constructive characterization of trees which satisfy the $\alpha$=$\betta$ equality. The proof of our main theorem is based on a new decomposition algorithm obtained for trees.

22 pages, 17 figures

References in corpus (6)

• On trees with a maximum proper partial 0-1 coloring containing a maximum matching
• On complexity of special maximum matchings constructing
• A note on minimal matching covered graphs
• On Edge-Disjoint Pairs Of Matchings
• Characterization Of A Class Of Graphs Related To Pairs Of Disjoint Matchings
• Two polynomial algorithms for special maximum matching constructing in trees