Bubble-sort网络的一类条件连通度  

A kind of conditional connectivity of bubble-sort networks

作　　者：郭利涛[1] 林超 GUO Litao;LIN Chao(School of Mathematics and Statistics,Xiamen University of Technology,Xiamen 361024,China;School of Urban Construction and Management,Xiamen City University,Xiamen 361008,China)

机构地区：[1]厦门理工学院数学与统计学院,福建厦门361024 [2]厦门城市职业学院城市建设与管理学院,福建厦门361008

出　　处：《厦门大学学报（自然科学版）》2024年第2期335-338,共4页Journal of Xiamen University：Natural Science

基　　金：国家自然科学基金(11961051);厦门市自然科学基金(3502Z202373060)。

摘　　要：[目的]为评价网络容错性,以具有高对称性和递归结构的Bubble-sort网络为研究对象,确定其h-extra r-分支边连通度.[方法] Bubble-sort网络Bn可以分解成n个子图Bn(i),其中Bn(i)是由点集{x_(1)x_(2)…x_(n):x_(n)=i}(1≤i≤n)导出的子图,并且Bn(i)同构于B_(n-1),利用它的结构特点,用数学归纳法推理证明了主要结果.[结果]确定了bubble-sort网络的h-extra r-分支边连通度cλ2/3(B_(n))=4n-10(n≥4).[结论]研究了bubble-sort网络的一类条件连通度,可用于衡量网络的可靠性.今后将继续深入研究bubble-sort网络的其他条件连通度.[Objective]As one of intensively-investigated research topics in network fault tolerance,the bubble-sort network secures good properties,such as high symmetry and recursive structure.Herein,we determine the h-extra r-component edge connectivity of bubble-sort networks.[Methods]The bubble-sort graph B_(n) can be partitioned into n subgraphs B_(n)(i),where B_(n)(i)denotes the induced subgraph by the set of vertex{x_(1)x_(2)…x_(n):x_(n)=i}for 1≤i≤n and isomorphic to B_(n)-1.According to its structural characteristics,we use mathematical induction to infer and prove main results.[Results]We determine the h-extra r-component edge connectivity of bubble-sort networks,i.e.cλ2/3(B_(n))=4n-10(n≥4).[Conclusions]The conditional connectivity can be used to measure the reliability of a network.We investigate a type of conditional connectivity of bubble-sort networks,and plan to continue studying other conditional connectivities of bubble-sort networks in the future.

关 键 词：条件连通度 Bubble-sort网络 边割 

分 类 号：O157[理学—数学]