Some topological and combinatorial properties of WK-recursive mesh and WK-pyramid interconnection networks

摘要

The WK-recursive mesh and WK-pyramid networks are recursively defined hierarchical interconnection networks with excellent properties which well idealize them as alternatives for mesh and traditional pyramid interconnection topologies. They have received much attention due to their favorable attributes such as small diameter, large connectivity, and high degree of scalability and expandability. In this paper, we deal with pancyclicity and surface area of these networks. These properties are of great importance in the implementation of a variety of parallel algorithms in multicomputers. We show that WK-recursive mesh network is I-partially pancyclic, i.e. any cycle of length 3, 4, 6,..., and N can be constructed in the WK-recursive mesh. Also, we prove that the WK-pyramid is pancyclic, that is all cycles of length 3, 4,..., and N can be formed in a WK-pyramid. It is also proved that two link-disjoint Hamiltonian paths/cycles can be embedded in the WK-recursive mesh[WK-pyramid. We then study the surface area of WK-recursive mesh and WK-pyramid networks and put forth some equations for calculating the surface area in these networks. (C) 2008 Elsevier B.V. All rights reserved.