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 K<inf>5</inf> 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 (K<inf>3</inf>-free) graphs. The extremal graphs, in this case, are known to be the disjoint unions of copies of K<inf>3,3</inf>. Along the same line, we study the maximum number of maximal induced matchings when the graphs are restricted to K<inf>5</inf>-free graphs and K<inf>4</inf>-free graphs. We show that every K<inf>5</inf>-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 K<inf>4</inf>. When the graphs are restricted to K<inf>4</inf>-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 W<inf>5</inf>. © 2024 The Author(s)