Embedding a mesh of trees in the crossed cube

Crossed cubes are an important class of variants of hypercubes as interconnection topologies in parallel computing. In this paper, we study the embedding of a mesh of trees in the crossed cube. Let n be a multiple of 4 and N = 2((n-2)/2). We prove that an N x N mesh of trees (containing 3N(2) - 2N nodes) can be embedded in an n-dimensional crossed cube (containing 4N(2) nodes) with dilation 1 and expansion about 4/3. This result shows that crossed cubes are promising interconnection networks since mesh of trees enables fast parallel computation. (C) 2012 Elsevier B.V. All rights reserved.