Embedding of Hypercubes into Generalized Books

Abstract

Graph embedding has been known as a powerful tool for implementation of parallel algorithms or simulation of different interconnection networks. An embedding $f$ of a guest graph $G$ into a host graph $H$ is a bijection on the vertices such that each edge of $G$ is mapped into a path of $H$. In this paper, we introduce a graph called the generalized book and the main results obtained are: (1) For $r\ge 3$, the minimum wirelength of embedding $r$-dimensional hypercube $Q_r$ into the generalized book $\mathrm{G}\mathrm{B}[2^{r_1},2^{r_2},2^{r_3}]$, where $r_1+r_2+r_3=r$. (2) A linear time algorithm to compute the exact wirelength of embedding hypercube into generalized book. (3) An algorithm for embedding hypercube into generalized book with dilation 3, proving that the lower bound obtained by Manuel et al. [28] is sharp.