An algorithm for embedding Turán graphs into incomplete hypercubes with minimum wirelength

Abstract

The wirelength is one of the key parameters of the quality of embedding graphs into host graphs. To our knowledge, no results for computing the wirelength of embedding irregular graphs into irregular graphs are known in the literature. We develop an algorithm that determines the wirelength of embedding of the Turán graph $T(\ell, 2^p)$, where $2^{n-1} \leq \ell < 2^{n}$ and $1\le p\le \lceil \log_2 \ell\rceil\leq n$, into the incomplete hypercube $I^{\ell}_{n}$. Incomplete hypercubes form an important generalization of hypercubes because they eliminate the restriction on the number of nodes in a system.