On the $\mathrm{\Delta }$-edge stability number of graphs

The $\mathrm{\Delta }$-edge stability number ${\mathrm{e}\mathrm{s}}_{\mathrm{\Delta }}(G)$ of a graph $G$ is the minimum number of edges of $G$ whose removal results in a subgraph $H$ with $\mathrm{\Delta }(H)=\mathrm{\Delta }(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 ${\mathrm{e}\mathrm{s}}_{\mathrm{\Delta }}(G)\le c\mathrm{\mid }V(G)\mathrm{\mid }$ for an arbitrary graph $G$ of given maximum degree $\mathrm{\Delta }$, where $c$ is a given constant, it suffices to prove the bound for $\mathrm{\Delta }$-regular graphs. Sharp upper bounds of this form are derived for regular graphs. It is proved that if $\mathrm{\Delta }(G)\ge \frac{\mathrm{\mid }V(G)\mathrm{\mid }-2}{3}$ or the induced subgraph on maximum degree vertices has a $\mathrm{\Delta }(G)$-edge coloring, then ${\mathrm{e}\mathrm{s}}_{\mathrm{\Delta }}(G)\le \lceil \mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}2\rceil$.