Induced matchings in subcubic graphs without short cycles

An induced matching of a graph G is a set M of edges of G such that every two vertices of G that are incident with distinct edges in M have distance at least 2 in G . The maximum number of edges in an induced matching of G is the induced matching number ν s ( G ) of G . 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. w that if G is a connected graph of order n ( G ) , maximum degree at most 3, girth at least 6, and without a cycle of length 7, then ν s ( G ) ≥ n ( G ) − 1 5 , and we characterize the graphs achieving equality in this lower bound.