Embedding a family of meshes into twisted cubes

The hypercube is one of the most popular interconnection networks since it has simple structure and is easy to implement. The twisted cube is an important variation of the hypercube. Let TQn denote the n-dimensional twisted cube. In this paper, we consider embedding a family of 2-dimensional meshes into a twisted cube. The main results obtained in this paper are: (1) For any odd integer n⩾1, there exists a mesh of size 2×2n−1 that can be embedded in the TQn with unit dilation and unit expansion. (2) For any odd integer n⩾5, there exists a mesh of size 4×2n−2 that can be embedded in the TQn with dilation 2 and unit expansion. (3) For any odd integer n⩾5, a family of two disjoint meshes of size 4×2n−3 can be embedded into the TQn with unit dilation and unit expansion. Results (1) and (3) are optimal in the sense that the dilations and expansions of the embeddings are unit values.