Complete path embedding in crossed cubes

Abstract—The crossed cube is an important variant of the hypercube. The n-dimensional crossed cube has only about half diameter, wide diameter, and fault diameter of those of the n-dimensional hypercube. Embeddings of trees, cycles, shortest paths, and Hamiltonian paths in crossed cubes have been studied in literature. Little work has been done on the embedding of paths except shortest paths, and Hamiltonian paths in crossed cubes. In this paper, we study optimal embedding of paths of different lengths between any two nodes in crossed cubes. We prove that paths of all lengths between dnþ12 e þ 1 and 2n 1 can be embedded between any two distinct nodes with a dilation of 1 in the n-dimensional crossed cube. The embedding of paths is optimal in the sense that the dilation of the embedding is 1. We also prove that dnþ12 e þ 1 is the shortest possible length that can be embedded between arbitrary two distinct nodes with dilation 1 in the n-dimensional crossed cube. Index Terms—Crossed cube, graph embedding, optimal embedding, interconnection network, parallel computing system.