Paths Embedding In Exchanged Hypercubes

An interconnection network is usually represented by a connected simple graph G=(V. E), where V is the set of processors and E is the set of communication links in the network. Graph embedding problem is one of the central issues in evaluating an interconnection network, and the important benifit of this problem is that we can apply existing algorithms for guest graphs to host graphs. The path is a simple network with low communication cost and distributed computation.The hypercube is one of the well-known topological structures of interconnection network. As a variant of the hypercube, the exchanged hypercube proposed by Loh et al, is a graph obtained by systematically removing links from a hypercube. It not only kept numerous desirable properties of the hypercube, but also reduced the intercon-nection complexity. The number of vertices in EH(s,t) is equal to that in hypercube Qs+t+i, but the ratio of the number of edges in EH(s,t) is almost half of Qs+t+i. Therefore, it is worth to investigate the properties of EH(s, t).In this thesis, we mainly studies the hamiltonian laceable, strongly hamiltonian laceable, wide diameter and fault diameter of EH (s, t). The conclusions are as follows.(Ⅰ) EH(s,t) is hamiltonian laceable and strongly hamiltonian laceable, when s,t≥2;(Ⅱ) The wide diameter dω(EH(s, t)) and fault diameter Dω(EH(s, t)) of EH(s, t) have following relations:...