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

Anush Tserunyan

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume309
Issue number4
DOIs
StatePublished - Mar 6 2009

Keywords

  • Matching
  • Maximum matching
  • Pair of disjoint matchings

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint 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