Characterization of a class of graphs related to pairs of disjoint matchings (Q1011703)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Characterization of a class of graphs related to pairs of disjoint matchings |
scientific article |
Statements
Characterization of a class of graphs related to pairs of disjoint matchings (English)
0 references
9 April 2009
0 references
For a given graph consider a pair of disjoint matchings whose union contains as many edges as possible. It is known that the ratio of the cardinalities of a maximum matching and the largest matching in these pairs is at most \(\frac{5}{4}\) and the bound is tight for this ratio (see [\textit{V. V. Mkrtchyan, V. L. Musoyan, A. V. Tserunyan}, ''On edge disjoint pairs of matchings.'' Discrete Math. 308, No. 23, 5823-5828 (2008; Zbl 1204.05080)]). The class of graphs for which the ratio is precisely \(\frac{5}{4}\) is characterized. It is shown that the graphs with that ratio equal to \(\frac{5}{4}\) are the graphs containing so-called spanning \(S\)-forests satisfying certain structural conditions. An \(S\)-forest is a graph whose each connected component is an \(S\)-spanner, which is a graph on 10 vertices consisting of two vertex-disjoint paths \(P_5\) with an edge joining the central vertices of these paths.
0 references
matching
0 references
pair of disjoint matchings
0 references
maximum matching
0 references