Bounding and approximating minimum maximal matchings in regular graphs

Julien Baste, Maximilian Fürst, Michael A. Henning, Elena Mohr, Dieter Rautenbach

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


The edge domination number γe(G) of a graph G is the minimum size of a maximal matching in G. It is well known that this parameter is computationally very hard, and several approximation algorithms and heuristics have been studied. In the present paper, we provide best possible upper bounds on γe(G) for regular and non-regular graphs G in terms of their order and maximum degree. Furthermore, we discuss algorithmic consequences of our results and their constructive proofs.

Original languageEnglish
Article number112243
JournalDiscrete Mathematics
Issue number3
Publication statusPublished - Mar 2021


  • Edge domination
  • Minimum maximal matching

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Bounding and approximating minimum maximal matchings in regular graphs'. Together they form a unique fingerprint.

Cite this