Dominating induced matchings and other graph parameters

A matching M in a graph G is an induced matching if the largest degree of the subgraph of G induced by M is equal to one. A dominating induced matching (DIM) of G is an induced matching that dominates every edge of G. It is well known that, if they exist, all dominating induced matchings of G are of the same size. The dominating induced matching number of G, denoted by dim(G), is the size of any dominating induced matching of G. In this paper, we continue the study of dominating induced matchings. We prove that, if G has a DIM, then the induced matching number of G is equal to the independence number of its line graph L(G) and to the edge domination number of G. It is also shown that dim(G)≤2 dim(L(G)), provided that both G and L(G) have a DIM. We also present some bounds on dim(G). In particular, for a tree T with a DIM we show that ⌈n−l+13⌉≤dim(T)≤⌊n−1+l3⌋, where l is the number of leaves. Moreover, for a regular graph G we establish some Nordhaus-Gaddum type bounds.