turkmath.org

Given a graph, the problem of finding the minimum size maximal matching (MMM) is also known as the (independent) edge dominating set (EDS) in the literature. We will give several results about the hardness of solving MMM in special graph classes and point out some future research questions in this direction. We will also talk about the related notion of equimatchable graphs: a graph is equimatchable if all maximal matchings of it have the same size. We will discuss about the structural properties of equimatchable graphs and point out interesting open questions in this area.