Conditional Connectivity of Bubble Sort Graphs

A subset F subset of V (G) is called an R (k) -vertex-cut of a graph G if G - F is disconnected and each vertex of G - F has at least k neighbors in G - F. The R-k -vertex-connectivity of G, denoted by kappa(k) (G), is the cardinality of a minimum R-k -vertex-cut of G. Let B (n) be the bubble sort graph of dimension n. It is known that kappa (k) (B (n) ) = 2 (k) (n - k - 1) for n >= 2k and k = 1, 2. In this paper, we prove it for k = 3 and conjecture that it is true for all k is an element of N. We also prove that the connectivity cannot be more than conjectured.