On edge-disjoint pairs of matchings

V. V. Mkrtchyan; V. L. Musoyan; A. V. Tserunyan

doi:10.1016/j.disc.2007.09.061

On edge-disjoint pairs of matchings

V. V. Mkrtchyan, V. L. Musoyan, A. V. Tserunyan

Research output: Contribution to journal › Article › peer-review

Abstract

For a graph G, consider the pairs of edge-disjoint matchings whose union consists of as many edges as possible. Let H be the largest matching among such pairs. Let M be a maximum matching of G. We show that 5/4 is a tight upper bound for | M | / | H |.

Original language	English (US)
Pages (from-to)	5823-5828
Number of pages	6
Journal	Discrete Mathematics
Volume	308
Issue number	23
DOIs	https://doi.org/10.1016/j.disc.2007.09.061
State	Published - Dec 6 2008
Externally published	Yes

Keywords

Matching
Maximum matching
Pair of edge-disjoint matchings

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/j.disc.2007.09.061

Library availability

Discover UIUC Full Text

Cite this

@article{cc0206e9a98642a0a5eb5aaa766a516b,

title = "On edge-disjoint pairs of matchings",

abstract = "For a graph G, consider the pairs of edge-disjoint matchings whose union consists of as many edges as possible. Let H be the largest matching among such pairs. Let M be a maximum matching of G. We show that 5/4 is a tight upper bound for | M | / | H |.",

keywords = "Matching, Maximum matching, Pair of edge-disjoint matchings",

author = "Mkrtchyan, {V. V.} and Musoyan, {V. L.} and Tserunyan, {A. V.}",

note = "The work in this paper was supported by a grant of the Armenian National Science and Education Fund.",

year = "2008",

month = dec,

day = "6",

doi = "10.1016/j.disc.2007.09.061",

language = "English (US)",

volume = "308",

pages = "5823--5828",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "23",

}

TY - JOUR

T1 - On edge-disjoint pairs of matchings

AU - Mkrtchyan, V. V.

AU - Musoyan, V. L.

AU - Tserunyan, A. V.

N1 - The work in this paper was supported by a grant of the Armenian National Science and Education Fund.

PY - 2008/12/6

Y1 - 2008/12/6

N2 - For a graph G, consider the pairs of edge-disjoint matchings whose union consists of as many edges as possible. Let H be the largest matching among such pairs. Let M be a maximum matching of G. We show that 5/4 is a tight upper bound for | M | / | H |.

AB - For a graph G, consider the pairs of edge-disjoint matchings whose union consists of as many edges as possible. Let H be the largest matching among such pairs. Let M be a maximum matching of G. We show that 5/4 is a tight upper bound for | M | / | H |.

KW - Matching

KW - Maximum matching

KW - Pair of edge-disjoint matchings

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

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

U2 - 10.1016/j.disc.2007.09.061

DO - 10.1016/j.disc.2007.09.061

M3 - Article

AN - SCOPUS:53049105120

SN - 0012-365X

VL - 308

SP - 5823

EP - 5828

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 23

ER -

On edge-disjoint pairs of matchings

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this