Some Properties Of Locally Twisted Cubes

When one design and select a topological structure for an interconnection network, fault tolerance is a significant criterion for evaluating the performance of the network. Maximum fault tolerance is always one of the major principles pursued by network designers. We consider the effect on reliability caused by hardware failures from the topological structure of network, that is, the reliability of data transmission when there are faulty vertices and(or) edges. Under this concept, the terms "fault tolerance" means when how many failures exist does the remained subnetwork still contain some special structure and perform correctly. Since vertex faults and(or) edge faults may happen when a network is used, it is practically meaningful to consider faulty networks.The hypercube is one of the most popular, versatile and efficient topological struc-tures of interconnection network at present. As an important variant of Qn, the locally twisted cube LTQn, first proposed by Yang et al, has many attractive properties as those of the hypercube. They have the same number of vertices and edges, n-regularity, n-connective and a simple recursive structure. Furthermore, LTQn has some properties superior to Qn. For example, the diameter of LTQn is approximately one half of the diameter of Qn, and LTQn contains cycles with any length l for 4≤l≤2n. Therefore, it is worth to research more properties of LTQn.This dissertation mainly studies the fault tolerant problems of LTQn, say, fault diameter, wide diameter and paths in the faulty LTQn. The conclusions are as follows (Ⅰ) A path of length l can be embedded between any two distinct vertices in LTQn-F for any faulty set F (?) V(LTQn)∪E(LTQn) with|F|≤n-3 and any integer l with 2n-1-1≤l≤|V(LTQn-F)|-1 for any integer n≥3; (Ⅱ) The fault diameter and the wide diameter of LTQn are the same, which is...