A CYCLE EMBEDDING ALGORITHM ON MBIUS CUBE INTERCONNECTION NETWORKS

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）.