Cycle Embedding In Crossed Cubes With Conditional Edge Faults

The hypercube is one of the most famous and attractive network topologies. It has been stuied a lot and have many nice properties such as regularity, symmetry, strong connectivity, embeddability, hamiltonicity, recursive construction and fault tolerance. On the other hand, the crossed cube, which is a variation of the hypercube, possesses some properties superior to the hypercube. For example, the diameter of the crossed cube is approximately half of the hypercube, the mean distance of the crossed cube is smaller than the hypercube.One of the important factor to evaluate an interconnection network is to study how well other existing networks can be embedded into this network. The pancycle-embedding problem deals with all possible lengths of the cycles in a given interconnection network. Component failures are inevitable when a network is put in use. Therefore, it is practically meaningful to consider faulty networks.In this dissertation, we main discuss the conditional fault tolerance, embedding cycle and a kind of automorphism of the crossed cube.In1995, Kulasinghe P et al showed that the crossed cube CQn is not vertex-transitive for n>5. For the crossed cube research, this flaws bring many inconvenience. Therefore, this thesis first determined a kind of automorphism of the crossed cube and proofed that these automorphism form a group, moreover using this automorphism group got crossed cube node classification. This result can provide more reliable theoretical bases for panconnectivity of crossed cube.Based on the problem of conditional link faults, The other part of this dissertation mainly discussed embedding cycles in crossed cube. Crossed cube is not as Hypercube as symmetric, and it is very difficult to construct a fault-free Hamiltonian cycle in the faulty crossed cube. So we take fully advantage of the Predecessors’experience and constructive approaches to obtain some auxiliary lemmas. We mainly developed the classical mathematical proof method, induction, to prove the theom. In this dissertation, we show that in the crossed cube CQn(n≥5), with at most2n-7faulty edges and each vertex is incident with at least two fault-free edges, there exists a fault-free cycle of length l in CQn for every l with4≤l≤2n. In2007, Hao-Shun Hung et al showed the probability that each node in such a faulty crossed cube CQn, is incident with at least two fault-free links. This further shows that we assumption is meaningful, for its occurrence probability is very close to1.