Stability Theorems for Graph Vulnerability Parameters

Given a graph property P, Bondy and Chvátal defined P to be k-stable if for any nonadjacent u, v∈ V(G) , whenever G+ uv has the property P and d(u) + d(v) ≥ k, then G itself has the property P. The smallest such k is called the stability ofP. We consider the graph parameters integrity, toughness, tenacity, and binding number. For each of these parameters, we provide the stability for the property that G has a value for that parameter which is at least c, for some fixed c. We also demonstrate how stability can lead to degree sequence theorems and compare these results to known degree sequence theorems that are best possible in a certain sense.