Linear Wirelength of Folded Hypercubes

Manuel et al. (Discret. Appl. Math. 157(7):1486–1495, 2009) obtained the exact wirelength of an r-dimensional hypercube into a path as well as a 2^?r/2?×2^ér/2ù{2^{lfloor r/2rfloor}times 2^{lceil r/2rceil}} grid and conjectured the same for a folded hypercube. In this paper we solve the edge isoperimetric problem for folded hypercubes and thereby obtain the exact wirelength of folded hypercubes into paths. Further we compute the exact wirelength of the r-dimensional folded hypercubes into 2 ^k × 2 ^r−k grids.