Constructing the nearly shortest path in crossed cubes

A graph G is panconnected   if each pair of distinct vertices u,v∈V(G)u,v∈V(G) are joined by a path of length l   for all dG(u,v)⩽l⩽|V(G)|-1dG(u,v)⩽l⩽|V(G)|-1, where dG(u,v)dG(u,v) is the length of a shortest path joining u and v in G. Recently, Fan et. al. [J. Fan, X. Lin, X. Jia, Optimal path embedding in crossed cubes, IEEE Trans. Parall. Distrib. Syst. 16 (2) (2005) 1190–1200, J. Fan, X. Jia, X. Lin, Complete path embeddings in crossed cubes, Inform. Sci. 176 (22) (2006) 3332–3346] and Xu et. al. [J.M. Xu, M.J. Ma, M. Lu, Paths in Möbius cubes and crossed cubes, Inform. Proc. Lett. 97 (3) (2006) 94–97] both proved that n  -dimensional crossed cube, CQnCQn, is almost panconnected except the path of length dCQn(u,v)+1dCQn(u,v)+1 for any two distinct vertices u,v∈V(CQn)u,v∈V(CQn). In this paper, we give a necessary and sufficient condition to check for the existence of paths of length dCQn(u,v)+1dCQn(u,v)+1, called the nearly shortest paths, for any two distinct vertices u,vu,v in CQnCQn. Moreover, we observe that only some pair of vertices have no nearly shortest path and we give a construction scheme for the nearly shortest path if it exists.