20.500.12556/RUL-169012 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 deltapovezavno število stabilnosti prirejanje barvanje povezav true false true Angleški jezik Slovenski jezik Članek v reviji 2025-05-07 09:47:08 2025-05-07 09:47:12 2025-05-08 04:19:54 0000-00-00 00:00:00 2025 0 0 10 str. art. 104167 Vol. 127 Jun. 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 0195-6698 10.1016/j.ejc.2025.104167 234762499 1-s2.0-S0195669825000502-main.pdf 1-s2.0-S0195669825000502-main.pdf 1 FDA6A03266CF7C0296E574065AECBB44 dedd4b8fc645b702b52e797a4a43949f8de57c2cee2f767dc06fd14ff244e2f4 d2664752-2b16-11f0-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=210122 https://www.sciencedirect.com/science/article/pii/S0195669825000502 1 4b16a92c-2b16-11f0-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=210120 Fakulteta za matematiko in fiziko 0 0 0