Frei et al. [6] showed that the problem to decide whether a graph is stable with respect to some graph parameter under adding or removing either edges or vertices is $Theta_2^{text{P}}$-complete. They studied the common graph parameters $alpha$ (independence number), $beta$ (vertex cover number), $omega$ (clique number), and $chi$ (chromatic number) for certain variants of the stability problem. We follow their approach and provide a large number of polynomial-time algorithms solving these problems for special graph classes, namely for graphs without edges, complete graphs, paths, trees, forests, bipartite graphs, and co-graphs.
Download