pith. sign in

arxiv: 0708.2363 · v1 · submitted 2007-08-17 · 💻 cs.DM

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

classification 💻 cs.DM
keywords pairstreesalphabettacardinalitycharacterizationconstructivedefine
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.