拟正则图的最大线图连通度及其应用  

The Maximum Connectivity of the Line Graph over Quasi-regular Graphs and Its Application

作　　者：何中市[1] 杨晓帆[1] 陈四清[1] 

机构地区：[1]重庆大学计算机研究所

出　　处：《重庆大学学报（自然科学版）》1995年第2期21-26,共6页Journal of Chongqing University

基　　金：国家自然科学基金

摘　　要：引入了拟正则（ｐ，ｑ）图的最大线图连通度Ｒ（ｐ，ｑ），得到上、下界至多相差１的Ｒ（ｐ，ｑ）的取值范围：２ｍ－２≤Ｒ（ｐ，ｑ）≤２ｍ－其中（２ｑ）ｍｅｄｐ．将此结果应用于容错多总线系统的最优设计，提出了两类最优容错设计，推广了己有结果；并揭示出当处理机个数相对于总线条数较大时最优容错设计的广泛存在性。The maximum connectivity R(p,q)of the line graph over quasi-regular(p,q)graphs is discussed.A bound on R(p,q)2m-2≤R(p,q)presented,wherem:modp.Further two classes of fault tolerant multibus systems are proposed;As a result,the previous results are generalized;meanwhile,the wide-rangingexistence of the optimal fault tolerant design is revealed when the number of processors/thenumber of buses is large.

关 键 词：图连通性 拟正则图 线图 多总线系统 

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