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/

[1] C. Balbuena, X. Marcote and P. García-Vázquez, On restricted connectivities of permutation graphs, Networks 45 (2005) 113-118. doi: 10.1002/net.20056

[2] Zs. Baranyai, On the factorization of the complete uniform hypergraph, Colloq. Math. Soc. János Bolya 10 (1975) 91-108.

[3] F.T. Boesch, Synthesis of reliable networks - a survey, IEEE Trans. Reliability 35 (1986) 240-246. doi: 10.1109/TR.1986.4335424

[4] F.T. Boesch and R. Tindell, Circulants and their connectivities, J. Graph Theory 8 (1984) 487-499. doi: 10.1002/jgt.3190080406

[5] G. Boruzanlı Ekinci and J.B. Gauci, On the reliability of generalized Petersen graphs, Discrete Appl. Math., in press. doi: 10.1016/j.dam.2017.02.002

[6] G. Boruzanlı Ekinci and A. Kırlangi¸c, Super connectivity of Kronecker product of complete bipartite graphs and complete graphs, Discrete Math. 339 (2016) 1950-1953. doi: 10.1016/j.disc.2015.10.036

[7] B.-L. Chen and K.-W. Lih, Hamiltonian uniform subset graphs, J. Combin. Theory, Ser. B 42 (1987) 257-263. doi: 10.1016/0095-8956(87)90044-X

[8] F. Harary, Conditional connectivity, Networks 13 (1983) 347-357. doi: 10.1002/net.3230130303

[9] M.-C. Heydemann, Cayley graphs and interconnection networks, in: Graph Symmetry: Algebraic Methods and Applications, G. Hahn and G. Sabidussi (Ed(s)), (Springer, Dordrecht, 1997) 167-224. doi: 10.1007/978-94-015-8937-6 5

[10] L.-H. Hsu and C.-K. Lin, Graph Theory and Interconnection Networks (CRC Press, 2008).

[11] M. Kneser, Aufgabe 360, Jahresber. Dtsch. Math.-Ver. 58 (1955) 27.

[12] M. Lü, C. Wu, G.-L. Chen and C. Lv, On super connectivity of Cartesian product graphs, Networks 52 (2008) 78-87. doi: 10.1002/net.20224

[13] J.H. van Lint and R.M.Wilson, A Course in Combinatorics, 2nd edition (Cambridge University Press, Cambridge, 2001). doi: 10.1017/CBO9780511987045

[14] M.E. Watkins, Connectivity of transitive graphs, J. Combin. Theory 8 (1970) 23-29. doi: 10.1016/S0021-9800(70)80005-9

[15] W. Yang and J. Meng, Extraconnectivity of hypercubes, Appl. Math. Lett. 22 (2009) 887-891. doi: 10.1016/j.aml.2008.07.016

[16] W. Yang and J. Meng, Extraconnectivity of hypercubes (II), Australas. J. Combin. 47 (2010) 189-195.