A subset F V（G） is called an Rk-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 Rk-vertex-connectivity of G, denoted by κk（G）, is the cardinality ...A subset F V（G） is called an Rk-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 Rk-vertex-connectivity of G, denoted by κk（G）, is the cardinality of a minimum Rk-vertex-cut of G. Let Bn be the bubble sort graph of dimension n. It is known that κk（Bn） = 2k（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 ∈ N. We also prove that the connectivity cannot be more than conjectured.展开更多
基金Supported by Tsinghua University Initiative Scientific Research Program and Project 11771246 Supported by National Natural Science Foundation of China
文摘A subset F V（G） is called an Rk-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 Rk-vertex-connectivity of G, denoted by κk（G）, is the cardinality of a minimum Rk-vertex-cut of G. Let Bn be the bubble sort graph of dimension n. It is known that κk（Bn） = 2k（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 ∈ N. We also prove that the connectivity cannot be more than conjectured.
