Fault-Tolerance Research Of Locally Twisted Cubes And Crossed Cubes

In the study of interconnection network topology, using diagrams to model the structure have been widely used by scholars. In the measure of fault-tolerant of network, the path embedding and pancyclicity has become a very important indicator. When a large network into use, inevitably there will be some failures, then in order to ensure that the rest of the network system can still work property, we need to consider how much the network can tolerate the components and (or) wiring errors occur simultaneously. Therefore, fault tolerance study has theoretical and practical significance. When an error occurs in the network, let F be the error collection in network structure.Locally twisted cubes LTQn and crossed cubes CQn are the variation of hypercube Qn, they possesses many desirable properties of Qn, while improving the shortcomings of hypercube, such as the pancyclicity, etc., when they have same points, their diameter length is half the hypercube. When design or select interconnection network topology structure for system, the fault-tolerance is a fundamental consideration, the relevant research on fault-tolerance also attracted the attention of scientists. To research the fault-tolerant properties of the locally twisted cubes and crossed cubes, the paper use the method that when n is relatively small, we use computer program to search and when n is large, we use the mathematical induction to prove, and made the following results:(1) Given the definition of weakness vertex pair, and concluded:a path of length of l can be embedded between any two distinct vertices except the two vertices in weakness vertex pair in LTQn-F for any faulty set F(?)V(LTQn)∪E(LTQn) with |F|≤n-2 and any integer l with 2n-1≤l≤|V(LTQn-F)|-1 for any integer n≥ 5.(2) There is a cycle C of length l such that for any vertex u in LTQn-F, u is in C for any faulty set F(?)V(LTQn)∪E(LTQn) with |F|≤n-3 and any integer l with 4≤l≤2n-|Fv|,l≠5 for any integer n≥3.(3) There is a cycle C of length 1 such that for any vertex u in CQn-F, u is in C for any faulty set F(?)V(LTQn)∪ E(LTOn) with |F|≤n-3 and any integer 6≤l≤2n-|Fv|,l≠7 for any integer n≥3.