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)/2N=2(n−2)/2. We prove that an N×NN×N mesh of trees (containing 3N2−2N3N2−2N nodes) can be embedded in an n  -dimensional crossed cube (containing 4N24N2 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.

► Crossed cubes are an important class of variants of hypercubes as interconnection topologies in parallel computing. ► A mesh of trees can be embedded in a crossed cube with dilation 1 and expansion about 4/3. ► Crossed cubes are promising interconnection networks since mesh of trees enables fast parallel computation.