Conditional connectivity of bubble sort graphs |
| |
Authors: | Ling-sheng Shi Peng Wu |
| |
Institution: | 1.Department of Mathematical Sciences,Tsinghua University,Beijing,China |
| |
Abstract: | A subset F ? 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 κ 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 κ 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 ∈ N. We also prove that the connectivity cannot be more than conjectured. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|