Geodesic
Extremal graphs having no stable cutset
The electronic journal of combinatorics, Tome 20 (2013) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A stable cutset in a graph is a stable set whose deletion disconnects the graph. It was conjectured by Caro and proved by Chen and Yu that any graph with $n$ vertices and at most $2n-4$ edges contains a stable cutset. The bound is tight, as we will show 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. As a by-product, an algorithmic implication of our result will be pointed out.
DOI : 10.37236/2513
Classification : 05C35, 05C40, 05C70, 05C69, 05C75
Mots-clés : stable cutset, independent cutset, fragile graph, extremal graph 
@article{10_37236_2513,
     author = {Van Bang Le and Florian Pfender},
     title = {Extremal graphs having no stable cutset},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {1},
     doi = {10.37236/2513},
     zbl = {1266.05073},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2513/}
}
TY  - JOUR
AU  - Van Bang Le
AU  - Florian Pfender
TI  - Extremal graphs having no stable cutset
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2513/
DO  - 10.37236/2513
ID  - 10_37236_2513
ER  - 
%0 Journal Article
%A Van Bang Le
%A Florian Pfender
%T Extremal graphs having no stable cutset
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/2513/
%R 10.37236/2513
%F 10_37236_2513
Van Bang Le; Florian Pfender. Extremal graphs having no stable cutset. The electronic journal of combinatorics, Tome 20 (2013) no. 1. doi: 10.37236/2513

Cité par Sources :