Distinct sizes of maximal independent sets on graphs with restricted girth

Let G be a graph. If G has exactly r distinct sizes of maximal independent sets, G belongs to a collection called M r . If G ∈ M r and the distinct values of its maximal independent sets are consecutive, then G belongs to I r . The independence gap of G is the difference between the maximum and the minimum sizes of a maximal independent set in G . In this paper, we show that recognizing graphs in I r is NP-complete, for every integer r ≥ 3. On the other hand, we show that recognizing trees in M r can be done in polynomial time, for every r ≥ 1. Furthermore, we present characterizations of some graphs with girth at least 6 with independence gap at least 1, including graphs with independence gap r − 1, for r ≥ 2, belonging to I r . Moreover, we present a characterization of some trees in I 3 .