On the Super (Edge)-Connectivity of Generalized Johnson Graphs.

Let n , k and t be non-negative integers. The generalized Johnson graph G (n , k , t) is the graph whose vertices are the k -subsets of the set { 1 , 2 , ... , n } , and two vertices are adjacent if and only if they intersect with t elements. Special cases of generalized Johnson graph include the Kneser graph G (n , k , 0) and the Johnson graph G (n , k , k − 1). These graphs play an important role in coding theory, Ramsey theory, combinatorial geometry and hypergraphs theory. In this paper, we discuss the connectivity properties of the Kneser graph G (n , k , 0) and G (n , k , 1) by their symmetric properties. Specifically, with the help of some properties of vertex/edge-transitive graphs we prove that G (n , k , 0) (5 ≤ 2 k + 1 ≤ n) and G (n , k , 1) (4 ≤ 2 k ≤ n) are super restricted edge-connected. Besides, we obtain the exact value of the restricted edge-connectivity and the cyclic edge-connectivity of the Kneser graph G (n , k , 0) (5 ≤ 2 k + 1 ≤ n) and G (n , k , 1) (4 ≤ 2 k ≤ n) , and further show that the Kneser graph G (n , k , 0) (5 ≤ 2 k + 1 ≤ n) is super vertex-connected and super cyclically edge-connected. [ABSTRACT FROM AUTHOR]