Abstract:
The graph embedding is an important technique to study the capability of multiprocessor interconnection networks simulating other networks. The property of cycle embedding of a kind of interconnection networks recently introduced——the Mbius cubes is discussed. They are hypercube variants which give better properties than hypercubes. For example, the diameter of the n dimensional Mbius cube M n is about one half that of the n dimensional hypercube, the expected distance of M n is about two thirds that of the n dimensional hypercube, etc..It is proved that the Mbius cubes have another better property than hypercubes, i.e., any cycle of length l(4≤l≤2 n) can be embedded into the n dimensional MAKo¨D4bius M n(n≥2) and gives a constructing procedure, and also proves that the capability of M n’ s simulating ring networks is higher than that of the n dimensional hypercube (hypercubes do not contain odd cycles).