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.
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
SN - 0012-365X
VL - 309
SP - 693
EP - 713
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 4
ER -