The Maximum Number of Dominating Induced Matchings

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 ) ≤ 3 n 3; μ ( G ) ≤ 4 n 5provided G is triangle‐free; and μ ( G ) ≤ 4 n − 1 5provided n ≥ 9 and G is connected.