Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650141 | Discrete Mathematics | 2009 | 21 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Anush Tserunyan,