  The stability number of a graph G, denoted by alpha(G), is the cardinality of
a stable set of maximum size in G. A graph is well-covered if every maximal
stable set has the same size. G is a Koenig-Egervary graph if its order equals
alpha(G) + mu(G), where mu(G) is the cardinality of a maximum matching in G. In
this paper we characterize $\alpha ^{++}$-stable graphs, namely, the graphs
whose stability numbers are invariant to adding any two edges from their
complements. We show that a K\"{o}nig-Egerv\'{a}ry graph is $\alpha
^{++}$-stable if and only if it has a perfect matching consisting of pendant
edges and no four vertices of the graph span a cycle. As a corollary it gives
necessary and sufficient conditions for $\alpha ^{++}$-stability of bipartite
graphs and trees. For instance, we prove that a bipartite graph is $\alpha
^{++}$-stable if and only if it is well-covered and C4-free.
