Revisiting Extremal Graphs Having No Stable Cutsets
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915042243379200 |
|---|---|
| author | Rauch, Johannes Rautenbach, Dieter |
| author_facet | Rauch, Johannes Rautenbach, Dieter |
| contents | Confirming a conjecture posed by Caro, it was shown by Chen and Yu that every graph $G$ with $n$ vertices and at most $2n-4$ edges has a stable cutset, which is a stable set of vertices whose removal disconnects the graph. Le and Pfender showed that all graphs with $n$ vertices and $2n-3$ edges without stable cutset arise recursively glueing together triangles and triangular prisms along an edge or triangle. Le and Pfender's proof contains a gap, which we fill in the present article. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_00337 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Revisiting Extremal Graphs Having No Stable Cutsets Rauch, Johannes Rautenbach, Dieter Combinatorics Confirming a conjecture posed by Caro, it was shown by Chen and Yu that every graph $G$ with $n$ vertices and at most $2n-4$ edges has a stable cutset, which is a stable set of vertices whose removal disconnects the graph. Le and Pfender showed that all graphs with $n$ vertices and $2n-3$ edges without stable cutset arise recursively glueing together triangles and triangular prisms along an edge or triangle. Le and Pfender's proof contains a gap, which we fill in the present article. |
| title | Revisiting Extremal Graphs Having No Stable Cutsets |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.00337 |