The Maximum Number of Dominating Induced Matchings

Abstract

A matching M of a graph G is a dominating induced matching (DIM) of G if every edge of G is either in M or adjacent with exactly one edge in M. We prove sharp upper bounds on the number μ(G) of DIMs of a graph G and characterize all extremal graphs. Our results imply that if G is a graph of order n, then μ(G) ≤ 3n 3 ; μ(G) ≤ 4n 5 provided G is triangle-free; and μ(G) ≤ 4n−1 5 provided n ≥ 9 and G is connected.