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 <= 2k + 1 <= n) and G(n, k, 1) (4 <= 2k <= 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 <= 2k + 1 <= n) and G(n, k, 1) (4 <= 2k <= n), and further show that the Kneser graph G(n, k, 0) (5 <= 2k + 1 <= n) is super vertex-connected and super cyclically edge-connected.