Characterization Of A Class Of Graphs Related To Pairs Of Disjoint Matchings

Details Characterization Of A Class Of Graphs Related To Pairs Of Disjoint Matchings Characterization Of A Class Of Graphs Related To Pairs Of Disjoint Matchings

2007-12-06

arxiv.org/abs/0712.1014v1

Discrete Mathematics 309 (2009) 693--713

Computer Science

Discrete Mathematics

33 pages, 10 figures

Scientific paper

10.1016/j.disc.2008.01.004

For a given graph consider a pair of disjoint matchings the union of which contains as many edges as possible. Furthermore, consider the relation of the cardinalities of a maximum matching and the largest matching in those pairs. It is known that this relation does not exceed 5/4 for any graph. We characterize the class of graphs for which this relation is precisely 5/4. Our characterization implies that these graphs contain a spanning subgraph, every component of which is the minimal graph of this class.

Affiliated with

Also associated with

No associations

Rating

Characterization Of A Class Of Graphs 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 Characterization Of A Class Of Graphs Related To Pairs Of Disjoint Matchings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Characterization Of A Class Of Graphs Related To Pairs Of Disjoint Matchings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-92386