Revisiting Extremal Graphs Having No Stable Cutsets
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |