Revisiting Extremal Graphs Having No Stable Cutsets

Fuente: arXiv
Gespeichert in:
Bibliographische Detailangaben
Hauptverfasser: Rauch, Johannes, Rautenbach, Dieter
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