TY - JOUR

T1 - Characterization of a class of graphs related to pairs of disjoint matchings

AU - Tserunyan, Anush

N1 - Funding Information:
The current work is the main part of the author’s Master’s thesis defended in May 2007. It was supported by a grant of Armenian National Science and Education Fund.
Copyright:
Copyright 2009 Elsevier B.V., All rights reserved.

PY - 2009/3/6

Y1 - 2009/3/6

N2 - 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.

AB - 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.

KW - Matching

KW - Maximum matching

KW - Pair of disjoint matchings

UR - http://www.scopus.com/inward/record.url?scp=60149105372&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=60149105372&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2008.01.004

DO - 10.1016/j.disc.2008.01.004

M3 - Article

AN - SCOPUS:60149105372

VL - 309

SP - 693

EP - 713

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 4

ER -