Fault-Tolerance Research Of Locally Twisted Cubes

There are a lot of requirements in designing the topology of interconnection, in which connectivity is the basic requirement but not the only one. Many more stronger properties have been proposed by related scholars. For example, pancyclic and panconnected. A graph G of order n is pancyclic if it contains cycles of every length from g to n inclusively, where g=g(G)is the girth of G. A graph G of order n is said to be panconnected if for any pair of different vertices x and y with distance d in G there exists an xy-path of length l for any l with d≤l≤n-1. Edge and/or vertex failures are inevitable when alarge parallel computer system is put in use. Therefore, the fault-tolerant capacity of a network is a critical issue.In this paper,we research fault-tolerance of locally twisted cubes. The locally twisted cube LTQn, as a variation of the hypercube Qn, not only retains some favorable properties of Qn, such as:regularity and symmetry, but also possesses some embedding properties that Qn does not. For example, the diameter of LTQn is only about half of the diameter of Qn. Therefore, research of properties about local twisted cube networks attracted the attention of researchers. Combained the results of search algorithm, we give a induction proof of fault-tolerance properties of locally twisted cubes, and obtianed the important resluts as follow:(1) Let LTQn=L(?)R. If n≥4 then, for any vertex uL in L, there are n-2 strong neighbors SL2,SL3,...,SLn-I and one weak neighbor wL in L. Moreover, if wL is the weak neighbor of uL and SLi is the strong neighbor of uL,then d(wR,uR)= 2 and there is not have a path of length 2 between uR and SRi. The same conclusion holds for any vertex uR in R.(2) If|F|≤n-3 and n≥3 then, for any fault-free edge e in LTQn and any integer l with 6≤l≤2n-|Fv|, there is a fault-free cycle of length l containing the edge e in LTQn-F.(3) 3≤n≤4, LTQn is n-3 fault-tolerant hamiltonian-connected,and n≥5, LTQn is 2n-8 edge fault-tolerant hamiltonian-connected, if each vertex is incident to at least three fault-free edges.