On the $\Delta$-edge stability number of graphs

Akbari, Saieed (avtor), Hosseini Dolatabadi, Reza (avtor), Jamaali, Mohsen (avtor), Klavžar, Sandi (avtor), Movarraei, Nazanin (avtor)

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}$.

• Jezik: Angleški jezik
• Ključne besede: vertex degree, $\Delta$-edge stability number, matching, edge coloring
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2025
• Št. strani: 10 str.
• Številčenje: Vol. 127, art. 104167
• PID: 20.500.12556/RUL-169012
• UDK: 519.17
• ISSN pri članku: 0195-6698
• DOI: 10.1016/j.ejc.2025.104167
• COBISS.SI-ID: 234762499
• Datum objave v RUL: 07.05.2025

Gradivo je del revije

• Naslov: European journal of combinatorics
• Skrajšan naslov: Eur. j. comb.
• Založnik: Elsevier
• ISSN: 0195-6698
• COBISS.SI-ID: 25427968

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: stopnja vozlišča, deltapovezavno število stabilnosti, prirejanje, barvanje povezav