20.500.12556/DiRROS-22176 On the $\Delta$-edge stability number of graphs The $\Delta$-edge stability number ${\rm es}_{\Delta}(G)$ of a graph $G$ is the minimum number of edges of $G$ whose removal results in a subgraph $H$ with $\Delta(H) = \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 ${\rm es}_{\Delta}(G) \leq c |V(G)|$ for an arbitrary graph $G$ of given maximum degree $\Delta$, where $c$ is a given constant, it suffices to prove the bound for $\Delta$-regular graphs. Sharp upper bounds of this form are derived for regular graphs. It is proved that if $\Delta(G) \geq\frac{|V(G)|-2}{3}$ or the induced subgraph on maximum degree vertices has a $\Delta(G)$-edge coloring, then ${\rm es}_{\Delta}(G) \le {\lceil |V(G)|/2\rceil}$. vertex degree ▫$\Delta$▫-edge stability number matching edge coloring stopnja vozlišča Delta-povezavno število stabilnosti prirejanje barvanje povezav true false true Angleški jezik Slovenski jezik Neznano 2025-05-07 10:38:17 2025-05-07 10:38:17 2025-10-24 03:50:43 0000-00-00 00:00:00 2025 0 0 10 str. [article no.] 104167 Vol. 127 Jun. 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2025-06-01 519.17 0195-6698 10.1016/j.ejc.2025.104167 234762499 1-s2.0-S0195669825000502-main.pdf 1-s2.0-S0195669825000502-main.pdf 1 0283BCF233BF6C5CFE16A9A51281BF8C f19452b2cd44f9e49b005b9586e86fdf15f28581a63d8e89466024069a654106 bf6c05d2-2b22-11f0-963a-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=32092 https://www.sciencedirect.com/science/article/pii/S0195669825000502 1 a1590d4b-2b1e-11f0-963a-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=32088 Inštitut za matematiko, fiziko in mehaniko 0 0 0