Embedding meshes into locally twisted cubes

As a newly introduced interconnection network for parallel computing, the locally twisted cube possesses many desirable properties. In this paper, mesh embeddings in locally twisted cubes are studied. Let LTQn(V, E) denote the n-dimensional locally twisted cube. We present three major results in this paper: (1) For any integer n ⩾ 1, a 2 × 2n−1 mesh can be embedded in LTQn with dilation 1 and expansion 1. (2) For any integer n ⩾ 4, two node-disjoint 4 × 2n−3 meshes can be embedded in LTQn with dilation 1 and expansion 2. (3) For any integer n ⩾ 3, a 4  × (2n−2 − 1) mesh can be embedded in LTQn with dilation 2. The first two results are optimal in the sense that the dilations of all embeddings are 1. The embedding of the 2 × 2n−1 mesh is also optimal in terms of expansion. We also present the analysis of 2p × 2q mesh embedding in locally twisted cubes.