The H-extra Connectivity And H-extraconditional Diagnosability Ofinterconnection Network

Nowadays,the application of multiprocessor system is becoming more and more widely.The realization of its function mainly depends on the connections between nodes,that is,the interconnection network.The reliability estimation and fault diagnosis of the Internet are important for the design and maintenance of the system.The h-extra connectivity and h-extra conditional diagnosability are important measures for reliability estimation and fault diagnosis respectively.Bubble-sort star graphs have received much research because they have both bubble sort graphs and star graphs properties such as small diameter,symmetry,high fault tolerance,and so on.In this paper,the paper studies the minimum h-cluster degree,the h-extra connectivity and h-extra conditional diagnosability of bubble-sort star graphs under the PMC model by construction and contradiction method.For n 34 and n 36 : the 1,2-extra connectivity of bubble-sort star graphs equal their minimum 2,3-cluster degree,they are 4n-8 and6n-15 respectively;the 1,2-extra conditional diagnosability of bubble-sort star graphs under the PMC model equal their 1,2-extra connectivity plus h,they are 4n-7 and6n-13 respectively.In the following study,this paper will give an algorithm for the h-extra connectivity in the general simple graph.First,we give a minimum connected component determination algorithm MCDA,the number of vertices of the smallest connected component can be determined by determining the number of vertices for each connected component.On the basis of the MCDA algorithm,furtherly,we give the ECDA algorithm for the determining the h-extra connectivity in the general simple graph.And the algorithm is applied to the hypercubes and bubble-sort star graphs,the results show that the result of the algorithm is consistent with the theoretical proof.Finally,the paper determines the h-extra conditional diagnosability of the general simple graphs under the PMC model,which can be proved by construction and contradiction method.The results show that: the h-extra conditional diagnosability of a simple graph in the PMC model equals to the h-extra connectivity when the minimum h+1-cluster degree equals the h-extra connectivity.