Dominating induced matchings and other graph parameters

Abstract

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 [Formula: see text], 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 [Formula: see text], provided that both G and L(G) have a DIM. We also present some bounds on [Formula: see text]. In particular, for a tree T with a DIM we show that [Formula: see text], where l is the number of leaves. Moreover, for a regular graph G we establish some Nordhaus-Gaddum type bounds.

Keywords

• Domination
• induced matching
• dominating induced matching
• maximal matching
• saturation number