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
    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
    0 references
    matching
    0 references
    pair of disjoint matchings
    0 references
    maximum matching
    0 references
    0 references
    0 references