The Super-Connectivity of Kneser Graphs

Discussiones Mathematicae Graph Theory

Gauci John Baptist¹  Ekinci Gülnaz Boruzanli² 

[1] Department of Mathematics, Faculty of Science University of Malta,Msida, Malta;Ekinci Department of Mathematics, Faculty of Science Ege University, Bornova,Izmir, Turkey;

关键词: connectivity;    super-connectivity;    kneser graphs;    05c40;    94c15;   

DOI  :  10.7151/dmgt.2051

来源: DOAJ

【 摘 要 】

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 n ( n/2) − 6 when n ≥ 6.

【 授权许可】

Unknown