【摘要】：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 ≥ 2 k 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.
[Abstract]:......
【作者單位】： Department
【基金】：Supported by Tsinghua University Initiative Scientific Research Program and Project 11771246 Supported by National Natural Science Foundation of China
【分類號】：O157.5

【相似文獻】

相關期刊論文 前10條

1 楊玲玲,李松臣;Enumeration of a Special Kind of Labeled Connected Graphs[J];Transactions of Tianjin University;2004年03期

2 張存銓;PATHS AND CYCLES IN ORIENTED GRAPHS[J];A Monthly Journal of Science;1981年10期

3 劉彥佩;ENUMERATION OF NONSEPARABLE OUTERPLANAR MAPS WITH VERTEX PARTITION[J];Science Bulletin;1987年24期

4 吳建良,苗蓮英;The Linear Arboricity of Graphs[J];數學進展;1998年06期

5 胡代強,吳建良;On the Coloring of Series-Parallel Graphs[J];數學進展;1999年02期

6 YEH Yeong-Nan;;On the number of matchings of graphs formed by a graph operation[J];Science in China(Series A:Mathematics);2006年10期

7 ;Effects of Vertex Activity and Self-organized Criticality Behavior on a Weighted Evolving Network[J];Communications in Theoretical Physics;2008年08期

8 ;2-Walk Linear Graphs with Small Number of Cycles[J];Wuhan University Journal of Natural Sciences;2010年05期

9 雷敏;趙清貴;侯振挺;;Three vertex degree correlations of fixed act-size collaboration networks[J];Journal of Central South University of Technology;2011年03期

10 阮愛武;李文昌;項傳銀;宋江民;康實;廖永波;;Graph theory for FPGA minimum configurations[J];半導體學報;2011年11期

相關會議論文 前10條

1 ;Fast parallel DNA algorithms for domination in graph[A];第三屆中國智能計算大會論文集[C];2009年

2 ;Weighted Scale-free Network with Widely Weighted Dynamics[A];中國自動化學會控制理論專業(yè)委員會C卷[C];2011年

3 Jinfang Han;;New Necessary and Sufficient Conditions for Schur D-Stability of Matrices[A];2013年中國智能自動化學術會議論文集（第一分冊）[C];2013年

4 ;Collective Consensus and Connectivity Maintenance of Flocking with Dynamical Networks[A];第七屆全國網絡科學論壇論文集[C];2011年

5 Hongbo Li;Wenjing Geng;Yu Wu;Xian Wang;;An Improved Force-Directed Algorithm Based on Emergence for Visualizing Complex Network[A];2013年中國智能自動化學術會議論文集（第二分冊）[C];2013年

6 Yang Jianfang;Jiang Juan;;Reverse 1-median Problem with Constraint in Trees[A];2012年計算機應用與系統建模國際會議論文集[C];2012年

7 Kee Bernard;;ADAPTIVE MESHFREE STRONG FORM METHODS[A];中國力學學會學術大會'2005論文摘要集（下）[C];2005年

8 ;Approximation of dense-n/2-subgraph and table compression problems[A];中國運籌學會第七屆學術交流會論文集（下卷）[C];2004年

9 ;An Efficient Route Computation Approach for Large Graphs[A];中國自動化學會控制理論專業(yè)委員會C卷[C];2011年

10 ;A Hypergraph Model for Clustering Scale-free Network[A];第二十七屆中國控制會議論文集[C];2008年

相關博士學位論文 前4條

1 張曉巖;最小全一問題的解及其算法的研究[D];南開大學;2006年

2 劉巖;關于圖的最大匹配問題的若干結果[D];鄭州大學;2000年

3 胡玉梅;廣義Randi（?）指標極值圖問題的研究[D];南開大學;2006年

4 魯紅亮;圖因子及相關問題[D];南開大學;2010年

相關碩士學位論文 前1條

1 王斌;圖的維數和基的構造[D];新疆大學;2002年

，

本文編號：2505817