Distinct sizes of maximal independent sets on graphs with restricted girth

Instituto de Informática – Universidade Federal de Goiás, Goiânia, Brazil

^* Corresponding author: jullianonascimento@ufg.br

Received: 9 January 2024
Accepted: 10 May 2024

Abstract

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₃.