The p-restricted edge-connectivity of Kneser graphs

摘要

Given a connected graph G and an integer 1 ≤ p ≤ ⌊|V(G)|/2⌋, a p-restricted edge-cut of G is any set of edges S ⊂ E(G), if any, such that G−S is not connected and each component of G−S has at least p vertices; and the p-restricted edge-connectivity of G, denoted λp(G), is the minimum cardinality of such a p-restricted edge-cut. When p-restricted edge-cuts exist, G is said to be super-λp if the deletion from G of any p-restricted edge-cut S of cardinality λp(G) yields a graph G−S that has at least one component with exactly p vertices. In this work, we prove that Kneser graphs K(n, k) are λp-connected for a wide range of values of p. Moreover, we obtain the values of λp(G) for all possible p and all n ≥ 5 when G=K(n,2). Also, we discuss in which cases λp(G) attains its maximum possible value, and determine for which values of p graph G=K(n,2) is super-λp.