Maximal induced matchings in K4-free and K5-free graphs

Abstract

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 10n/5≈1.5849n maximal induced matchings, and this bound is the best possible as any disjoint union of complete graphs K5 forms an extremal graph. It is also known that the bound drops to 3n/3≈1.4423n when the graphs are restricted to the class of triangle-free (K3-free) graphs. The extremal graphs, in this case, are known to be the disjoint unions of copies of K3,3. Along the same line, we study the maximum number of maximal induced matchings when the graphs are restricted to K5-free graphs and K4-free graphs. We show that every K5-free graph on n vertices has at most 6n/4≈1.5651n maximal induced matchings and the bound is the best possible obtained by any disjoint union of copies of K4. When the graphs are restricted to K4-free graphs, the upper bound drops to 8n/5≈1.5158n, and it is achieved by the disjoint union of copies of the wheel graph W5.