%A Dong-Fang Zhou, Jian-Xi Fan, Cheng-Kuan Lin, Bao-Lei Cheng, Jing-Ya Zhou, Zhao Liu
%T Optimal Path Embedding in the Exchanged Crossed Cube
%0 Journal Article
%D 2017
%J Journal of Computer Science and Technology
%R 10.1007/s11390-017-1729-8
%P 618-629
%V 32
%N 3
%U {https://jcst.ict.ac.cn/CN/abstract/article_2346.shtml}
%8 2017-05-05
%X The (*s* + *t* +1)-dimensional exchanged crossed cube, denoted as *ECQ*(*s*, *t*), combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that *ECQ*(*s*, *t*) has more attractive properties than other variations of the fundamental hypercube in terms of fewer edges, lower cost factor and smaller diameter. In this paper, we study the embedding of paths of distinct lengths between any two different vertices in *ECQ*(*s*, *t*). We prove the result in *ECQ*(*s*, *t*): if *s* > 3, *t* > 3, for any two different vertices, all paths whose lengths are between max{9, 「*s*+1/2」+「*t*+1/2」+4} and 2^{s+t+1}-1 can be embedded between the two vertices with dilation 1. Note that the diameter of *ECQ*(*s*, *t*) is *s*+1/2」+「*t*+1/2」+2. The obtained result is optimal in the sense that the dilations of path embeddings are all 1. The result reveals the fact that *ECQ*(*s*, *t*) preserves the path embedding capability to a large extent, while it only has about one half edges of *CQ*_{n}.