Tamanhos distintos de conjuntos independentes máximos em grafos com circuferência restrita

Seja G um grafo. Se G possui exatamente r tamanhos distintos de conjuntos independentes máximos, G pertence a uma coleção chamada M r . Se G ∈ M r e os valores distintos de seus conjuntos independentes máximos são consecutivos, então G pertence a I r . O intervalo de independência de G é a diferença entre o tamanho máximo e o mínimo de um conjunto independente máximo em G . Neste artigo, mostramos que reconhecer grafos em I r é NP-completo, para todo inteiro r ≥ 3. Por outro lado, mostramos que reconhecer árvores em M r pode ser feito em tempo polinomial, para todo r ≥ 1. Além disso, apresentamos caracterizações de alguns grafos com circuferência de pelo menos 6 com intervalo de independência de pelo menos 1, incluindo grafos com intervalo de independência r − 1, para r ≥ 2, pertencentes a I r . Além disso, apresentamos uma caracterização de algumas árvores em I 3 .