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.