Geodesic
Revisiting extremal graphs having no stable cutsets
The electronic journal of combinatorics, Tome 32 (2025) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 from recursively gluing together triangles and triangular prisms along an edge or triangle. Le and Pfender's proof (Electron. J. Combin. 20(1) (2013), #P54) contains a gap, which we fill in the present article.
DOI : 10.37236/13629
Classification : 05C40, 05C69, 05C35
Mots-clés : generating sequences 
@article{10_37236_13629,
     author = {Johannes Rauch and Dieter Rautenbach},
     title = {Revisiting extremal graphs having no stable cutsets},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {4},
     doi = {10.37236/13629},
     zbl = {8120111},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/13629/}
}
TY  - JOUR
AU  - Johannes Rauch
AU  - Dieter Rautenbach
TI  - Revisiting extremal graphs having no stable cutsets
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/13629/
DO  - 10.37236/13629
ID  - 10_37236_13629
ER  - 
%0 Journal Article
%A Johannes Rauch
%A Dieter Rautenbach
%T Revisiting extremal graphs having no stable cutsets
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/13629/
%R 10.37236/13629
%F 10_37236_13629
Johannes Rauch; Dieter Rautenbach. Revisiting extremal graphs having no stable cutsets. The electronic journal of combinatorics, Tome 32 (2025) no. 4. doi: 10.37236/13629

Cité par Sources :