Article ID Journal Published Year Pages File Type
4650141 Discrete Mathematics 2009 21 Pages PDF
Abstract
For a given graph consider a pair of disjoint matchings the union of which contains as many edges as possible. Furthermore, consider the ratio of the cardinalities of a maximum matching and the largest matching in those pairs. It is known that for any graph 54 is the tight upper bound for this ratio. We characterize the class of graphs for which it is precisely 54. Our characterization implies that these graphs contain a spanning subgraph, every connected component of which is the minimal graph of this class.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,