2024/11/30 by Johannes Rauch, Dieter Rautenbach, Rauch, Johannes +1 · 5 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2412.00337
openalex publication_date 2024/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.