The Effect of Vertex and Edge Deletion on the Number of Sizes of Maximal Independent Sets

Abstract

A graph \( G \) is said to be in the collection \( M_t \) if there are precisely \( t \) different sizes of maximal independent sets of vertices in \( G \). For \( G \in M_t \), and \( v \in G \), we determine the extreme values that \( x \) can assume where \( G \setminus \{v\} \) belongs to \( M_x \). For both the minimum and maximum values, graphs are given that achieve them, showing that the bounds are sharp. The effect of deleting an edge from \( G \) on the number of sizes of maximal independent sets is also considered.