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

Anush Tserunyan

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)693-713
Number of pages21
JournalDiscrete Mathematics
Issue number4
StatePublished - Mar 6 2009
Externally publishedYes


  • Matching
  • Maximum matching
  • Pair of disjoint matchings

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Characterization of a class of graphs related to pairs of disjoint matchings'. Together they form a unique fingerprint.

Cite this