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

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

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

• Language: English
• Keywords: vertex degree, $\Delta$-edge stability number, matching, edge coloring
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2025
• Number of pages: 10 str.
• Numbering: Vol. 127, art. 104167
• PID: 20.500.12556/RUL-169012
• UDC: 519.17
• ISSN on article: 0195-6698
• DOI: 10.1016/j.ejc.2025.104167
• COBISS.SI-ID: 234762499
• Publication date in RUL: 07.05.2025

Record is a part of a journal

• Title: European journal of combinatorics
• Shortened title: Eur. j. comb.
• Publisher: Elsevier
• ISSN: 0195-6698
• COBISS.SI-ID: 25427968

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: stopnja vozlišča, deltapovezavno število stabilnosti, prirejanje, barvanje povezav