Point Vulnerability Parameters And Diagnostic Degree Of Kronecker Product Graph

In the field of scientific and engineering computing,the computing of many major topics far exceeds the computing power of a single processor.Therefore,large-scale parallel computing systems have become the mainstream of highperformance computing.However,the larger the scale of the parallel computing system is,the greater the probability of the processors failure in the system is,and the more prominent the risk of the reliability of the system is.The reliability of a parallel computing system is often measured by its node vulnerability parameters of the vertices in it.In the early studies of node vulnerability parameters,most of the literature focused on the connectivity of networks.In addition,in order to ensure the efficient operation of the system,it is very important to timely and accurately identify the faulty processor in the system.The diagnosability is the maximum number of faulty processors that the system can identify at one time,which is also an important parameter to measure the reliability of the system interconnection network.The conventional connectivity and diagnosability allow all neighbors of some node to fail simultaneously,which is almost impossible in practical applications of massively parallel computing systems.In order to make up for the shortcomings of traditional connectivity and diagnosability,researchers first proposed the concepts of super connectivity and conditional diagnosability by restricting that at least one of all neighbors of any node in the system interconnection network can not fail.Afterwards,researchers further restricted the number of nodes in each fault-free component in the system interconnection network to be more than g,and proposed the concepts of g-extra connectivity and g-extra conditional diagnosability.In addition,noting that the connectivity cannot reflect the state of the remaining subnetworks after the network is destroyed.Some new node vulnerability parameters — toughness,dispersion,integrity,tenacity have been defined.The Kronecker product of graphs is an important method for constructing large-scale interconnection networks.In this paper,we study the super connectivity,g-extra connectivity,1-extra conditional diagnosability and some node vulnerability parameters of Kronecker product of complete multipartite graphs.Firstly,we investigate the super connectivity of the Kronecker product of the complete multipartite graph and the complete graph,and also study the g-extra connectivity of the Kronecker product of the complete balanced multipartite graph and the complete balanced multipartite graph.Next,we discuss the 1-extra conditional diagnosability of the Kronecker product of the complete multipartite graph and the complete graph.Finally,we explore some node vulnerability parameters of the Kronecker product of the complete multipartite graph and the complete multipartite graph,and determine its independent number,coverage number,connectivity,toughness,dispersion,integrity and tenacity.The research results of this paper can provide a certain theoretical basis for the reliability analysis and evaluation of large-scale interconnection networks.