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

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

引入了拟正则（ｐ，ｑ）图的最大线图连通度Ｒ（ｐ，ｑ），得到上、下界至多相差１的Ｒ（ｐ，ｑ）的取值范围：２ｍ－２≤Ｒ（ｐ，ｑ）≤２ｍ－其中（２ｑ）ｍｅｄｐ．将此结果应用于容错多总线系统的最优设计，提出了两类最优容错设计，推广了己有结果；并揭示出当处理机个数相对于总线条数较大时最优容错设计的广泛存在性。

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.