Maximal induced matchings in K₄-free and K₅-free graphs

An induced matching in a graph is a set of edges whose endpoints induce a 1-regular subgraph. It is known that every graph on n vertices has at most 10^n/5≈1.5849ⁿ maximal induced matchings, and this bound is the best possible as any disjoint union of complete graphs K₅ forms an extremal graph. It is also known that the bound drops to 3^n/3≈1.4423ⁿ when the graphs are restricted to the class of triangle-free (K₃-free) graphs. The extremal graphs, in this case, are known to be the disjoint unions of copies of K_3,3. Along the same line, we study the maximum number of maximal induced matchings when the graphs are restricted to K₅-free graphs and K₄-free graphs. We show that every K₅-free graph on n vertices has at most 6^n/4≈1.5651ⁿ maximal induced matchings and the bound is the best possible obtained by any disjoint union of copies of K₄. When the graphs are restricted to K₄-free graphs, the upper bound drops to 8^n/5≈1.5158ⁿ, and it is achieved by the disjoint union of copies of the wheel graph W₅.