The hypercube structure is a well-known interconnection model. As an important topology to interconnect multiprocessor systems, it has been proven to possess many attractive properties, and multiprocessor computers built with hypercube structure have been in existence for long time. Since its introduction many years ago, numerous variants of hypercube have been proposed. One of the most notable among them, the crossed cube, was first proposed by Efe [3], and has attracted much attention in the literature [1, 4, 6, 7, 8]. An n-dimensional crossed cube, denoted as CQ_n, is derived by "crossing" some links in an n-dimensional hypercube (n-cube for short). With exactly same hardware cost as hypercube, it has been shown that such a simple variation gains important benefits such as greatly reduced diameter.