On the Δ-edge stability number of graphs

The Δ-edge stability number esΔ(G) of a graph G is the minimum number of edges of G whose removal results in a subgraph H with Δ(H) = Δ(G)-1. Sets whose removal results in a subgraph with smaller maximum degree are called mitigating sets. It is proved that there always exists a mitigating set which induces a disjoint union of paths of order $2$ or $3$. Minimum mitigating sets which induce matchings are characterized. It is proved that to obtain an upper bound of the form esΔ(G) ≤ c |V(G)| for an arbitrary graph G of given maximum degree Δ, where c is a given constant, it suffices to prove the bound for Δ-regular graphs. Sharp upper bounds of this form are derived for regular graphs. It is proved that if Δ(G) ≥|V(G)|-2/3 or the induced subgraph on maximum degree vertices has a Δ(G)-edge coloring, then esΔ(G) ≤ |V(G)|/2.