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

R. R. Kamalian, V. V. Mkrtchyan

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.

Knowledge Graph



Sign up or login to leave a comment