On edge-disjoint pairs of matchings

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

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)5823-5828
Number of pages6
JournalDiscrete Mathematics
Volume308
Issue number23
DOIs
StatePublished - Dec 6 2008
Externally publishedYes

Keywords

  • Matching
  • Maximum matching
  • Pair of edge-disjoint matchings

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On edge-disjoint pairs of matchings'. Together they form a unique fingerprint.

Cite this