Conditional Connectivity of Bubble Sort Graphs

发布时间：2019-06-25 16:13

【摘要】：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];中国自动化学会控制理论专业委员会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];中国自动化学会控制理论专业委员会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