Some Properties Of Exchanged Hypercubes

It is well-known that a topological structure for an interconnection network can be modeled by a connected graph G= (V, E), where V is the set of processors and E is the set of communication links in the network. The network topology determines how well the processors can work cooperatively. One of the central issues in evaluating an interconnection network is to study if it contains cycles of all possible lengths. We con-sider 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 ex-changed hypercube EH(s, t), first proposed by Loh et al, is a graph obtained by sys-tematically removing links from a hypercube. It not only kept numerous desirable prop-erties of the hypercube, but also reduced the interconnection complexity. The number of vertices in EH(s, t) is equal to that in hypercube Qs+t+1, but the number of edges in EH(s,t) is almost half of hypercube Qs+t+1.Hence, the exchanged hypercube has fewer edges than the hypercube. Therefore, it is worth to investigate more properties of EH(s,t).This dissertation mainly studies the cycle embedding problem and edge-fault-tolerance of EH(s, t). The conclusions are as follows. (Ⅰ) Every edge of EH(s,t)(2≤s≤t)lies on an even l-cycle where 8≤l≤2s+t+1;(Ⅱ)For any subset F of E(EH(s,t))(2≤s≤t)with|F|≤s-1,EH(s,t)-F remains hamiltonian.