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 frac(5, 4) is the tight upper bound for this ratio. We characterize the class of graphs for which it is precisely frac(5, 4). Our characterization implies that these graphs contain a spanning subgraph, every connected component of which is the minimal graph of this class.
- Maximum matching
- Pair of disjoint matchings
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics