The Maximum Number of Dominating Induced Matchings
Min Chih Lin, Veronica A. Moyano, Dieter Rautenbach, Jayme Luiz SZWARCFITER · Journal of Graph Theory · 2014
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 of DIMs of a graph G and characterize all extremal graphs. Our results imply that if G is a graph of order n, then ; provided G is triangle‐free; and provided and G is connected.