Hybrid Diagnosis And Conditional Diagnosis Capability Analysis Of Graph

Fault tolerance and diagnosis capability of interconnection networks are param-eters to measure the ability of interconnection networks to transmit information.So,it is of great significance to study these properties.Graph as the model of intercon-nection networks,we can use the professional knowledge of graph theory to study the parameters of interconnection networks.So far,many parameters are proposed to evaluate the reliability and Transmission property of network structure.The connectivity and diagnosability of graph are classical evaluation parameters.As an extension of traditional connectivity,Fabrega and Fiol introduced g-extra connectivity.Let G=(V,E)be a simple and connected graph with vertex set V(G)and the edge set E(G).There F is a subset of V(G).If G-F is disconnection and every component has more than g vertices,then F is called a g-extra vertex cut.The g-extra connectivity κg(G)of a graph G is the cardinality of the smallest g-extra cut of G.With the proposal and solution of g-extra connectivity,g-extra conditional diagnosability of G has been proposed and denoted by tq(G).The g-extra conditional diagnosability of many interconnection networks has been determined under the PMC model and the MM*model.Note that the above parameters are only used to measure the diagnosis capabil-ity of a multiprocessor system without link faults.In fact,link faults may occur in the system.Thus,some researchers start to study the diagnosis capability of multi-processor systems with both node and link faults.In recent years,the diagnosability of graph G with fault links have obtained.It ia a natural question to ask how the diagnosability decreases if some links are missing for a multiprocessor system.To address the deficiency of the classical diagnosability and the above problem,Zhu et al.introduced the concept of h-edge tolerable diagnosability the(G).It is the minimum diagnosability of graphs G-F_e with F_e(?)E(G)and |F_e|≤h.In this paper,we frist prove that g-extra connectivity of DQcube is κg(DQ)=(g+1)(n+1)-g(g+3)/2 for 0≤g≤n-3 and then show that the g-extra conditional diagnosability of DQcube under the PMC model(n≥4,1≤g≤n-3)and the MM*model(n≥7,1≤g≤(n-3)/4)is tg(DQ)=(g+1)(n+1)-g(g+3)/2+g.Next,we prove that hybrid fault diagnosis capability analysis of graph.The diagnosability of a k-regular 2-cn graph with missing edges is δ(G-F_e)(where F_e (?) E(G)).