Geodesic
The Super-Connectivity of Kneser Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 5-11

Voir la notice de l'article provenant de la source Library of Science

A vertex cut of a connected graph G is a set of vertices whose deletion disconnects G. A connected graph G is super-connected if the deletion of every minimum vertex cut of G isolates a vertex. The super-connectivity is the size of the smallest vertex cut of G such that each resultant component does not have an isolated vertex. The Kneser graph KG(n, k) is the graph whose vertices are the k-subsets of 1, 2, . . ., n and two vertices are adjacent if the k-subsets are disjoint. We use Baranyai’s Theorem on the decompositions of complete hypergraphs to show that the Kneser graph KG are super-connected when n ≥ 5 and that their super-connectivity is n2 − 6 when n ≥ 6.
Keywords: connectivity, super-connectivity, Kneser graphs 
@article{DMGT_2019_39_1_a0,
     author = {Ekinci, G\"ulnaz Boruzanli and Gauci, John Baptist},
     title = {The {Super-Connectivity} of {Kneser} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {5--11},
     publisher = {mathdoc},
     volume = {39},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a0/}
}
TY  - JOUR
AU  - Ekinci, Gülnaz Boruzanli
AU  - Gauci, John Baptist
TI  - The Super-Connectivity of Kneser Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 5
EP  - 11
VL  - 39
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a0/
LA  - en
ID  - DMGT_2019_39_1_a0
ER  - 
%0 Journal Article
%A Ekinci, Gülnaz Boruzanli
%A Gauci, John Baptist
%T The Super-Connectivity of Kneser Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 5-11
%V 39
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a0/
%G en
%F DMGT_2019_39_1_a0
Ekinci, Gülnaz Boruzanli; Gauci, John Baptist. The Super-Connectivity of Kneser Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 5-11. http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a0/