The effect of vertex and edge deletion on the number of sizes of maximal independent sets

摘要

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 ∈M_t and v ∈ G, we determine the extreme values that x can assume where G{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.