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

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

2007-08-17

arxiv.org/abs/0708.2363v1

Computer Science

Discrete Mathematics

22 pages, 17 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On a constructive characterization of a class of trees related to pairs of disjoint matchings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On a constructive characterization of a class of trees related to pairs of disjoint matchings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On a constructive characterization of a class of trees related to pairs of disjoint matchings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-5985