Embedding hypercubes and folded hypercubes onto Cartesian product of certain trees

The hypercube network is one of the most popular interconnection networks since it has simple structure and is easy to implement. The folded hypercube is an important variation of the hypercube. Interconnection networks play a major role in the performance of distributed memory multiprocessors and the one primary concern for choosing an appropriate interconnection network is the graph embedding ability. A graph embedding of a guest graph G into a host graph H is an injective map on the vertices such that each edge of G is mapped into a path of H. The wirelength of this embedding is defined to be the sum of the lengths of the paths corresponding to the edges of G. In this paper we embed hypercube and folded hypercube onto Cartesian product of trees such as 1-rooted complete binary tree and path, sibling tree and path to minimize the wirelength.