An algorithm for embedding Turán graphs into incomplete hypercubes with minimum wirelength
A. Arul Shantrinal, Sandi Klavžar, T.M. Rajalaxmi, and R. Sundara Rajan
Vol. 25, no. 1, pp. 367-381, 2021. Regular paper.
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.

 This work is licensed under the terms of the CC-BY license.
Submitted: March 2020.
Reviewed: February 2021.
Revised: March 2021.
Reviewed: April 2021.
Revised: May 2021.
Accepted: June 2021.
Final: June 2021.
Published: June 2021.
Communicated by Antonios Symvonis
article (PDF)