Induced matchings in subcubic graphs without short cycles

An induced matching of a graph GG is a set MM of edges of GG such that every two vertices of GG that are incident with distinct edges in MM have distance at least 2 in GG. The maximum number of edges in an induced matching of GG is the induced matching number νs(G)νs(G) of GG. In contrast to ordinary matchings, induced matchings in graphs are algorithmically difficult. Next to hardness results and efficient algorithms for restricted graph classes, lower bounds are therefore of interest.We show that if GG is a connected graph of order n(G)n(G), maximum degree at most 3, girth at least 6, and without a cycle of length 7, then νs(G)≥n(G)−15, and we characterize the graphs achieving equality in this lower bound.