Maximal induced matchings in K4-free and K5-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 10n/5 approximate to 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 approximate to 1.4423nwhen 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 approximate to 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 approximate to 1.5158n, and it is achieved by the disjoint union of copies of the wheel graph W5. (c) 2024 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).