Bounding and approximating minimum maximal matchings in regular graphs

Abstract

The edge domination number ${\gamma }_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 ${\gamma }_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.