Conditional Vertex Connectivity Of Bubble Sort Graphs

A subset F V（G） is called an R^k-vertex-cut of G if G F is disconnected andeach vertex u∈V（G） F has at least k neighbors in G F. The R^k-vertex-connectivityof G, denoted by κ_k（G）, is the cardinality of a minimum R^k-vertex-cut of G. Let B_nbean n dimensional bubble sort graph, in this paper, we prove that κ₁（B_n）=2（n2）,κ₂（B_n）=4（n-3）, κ₃（B₅）=12, κ₃（B_n）=8（n-4） for n>5. We also prove thatκ_k（B_n）≤2^k（n-k-1） for n≥2k and conjecture that κ_k（B_n）=2^k（n-k-1） for n≥2k.