On the $Δ$-edge stability number of graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917133163692032 |
|---|---|
| author | Akbari, Saieed Dolatabadi, Reza Hosseini Jamaali, Mohsen Klavžar, Sandi Movarraei, Nazanin |
| author_facet | Akbari, Saieed Dolatabadi, Reza Hosseini Jamaali, Mohsen Klavžar, Sandi Movarraei, Nazanin |
| contents | The $Δ$-edge stability number ${\rm es}_Δ(G)$ of a graph $G$ is the minimum number of edges of $G$ whose removal results in a subgraph $H$ with $Δ(H) = Δ(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}_Δ(G) \leq c |V(G)|$ for an arbitrary graph $G$ of given maximum degree $Δ$, where $c$ is a given constant, it suffices to prove the bound for $Δ$-regular graphs. Sharp upper bounds of this form are derived for regular graphs. It is proved that if $Δ(G) \geq\frac{|V(G)|-2}{3}$ or the induced subgraph on maximum degree vertices has a $Δ(G)$-edge coloring, then ${\rm es}_Δ(G) \le \lceil |V(G)|/2\rceil$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_05254 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the $Δ$-edge stability number of graphs Akbari, Saieed Dolatabadi, Reza Hosseini Jamaali, Mohsen Klavžar, Sandi Movarraei, Nazanin Combinatorics The $Δ$-edge stability number ${\rm es}_Δ(G)$ of a graph $G$ is the minimum number of edges of $G$ whose removal results in a subgraph $H$ with $Δ(H) = Δ(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}_Δ(G) \leq c |V(G)|$ for an arbitrary graph $G$ of given maximum degree $Δ$, where $c$ is a given constant, it suffices to prove the bound for $Δ$-regular graphs. Sharp upper bounds of this form are derived for regular graphs. It is proved that if $Δ(G) \geq\frac{|V(G)|-2}{3}$ or the induced subgraph on maximum degree vertices has a $Δ(G)$-edge coloring, then ${\rm es}_Δ(G) \le \lceil |V(G)|/2\rceil$. |
| title | On the $Δ$-edge stability number of graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2403.05254 |