  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.

Combinatorics