Embedding complete binary trees into parity cubes

The complete binary tree as an important network structure has long been investigated for parallel and distributed computing, which has many nice properties and used to be embedded into other interconnection architectures. The parity cube is an important variant of the hypercube. It has many attractive features superior to those of the hypercube. In this paper, we prove that the complete binary tree with (Formula Presented.) vertices can be embedded with dilation 1, congestion 1, load 1 into the n-dimensional parity cube (Formula Presented.) and expansion tending to 1. Furthermore, we provide an (Formula Presented.) algorithm to construct the complete binary tree with (Formula Presented.) vertices in (Formula Presented.), where (Formula Presented.) denotes the number of vertices in (Formula Presented.) and (Formula Presented.).