Constructing the nearly shortest path in crossed cubes

A graph G is panconnected if each pair of distinct vertices image are joined by a path of length l for all image, where image 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, image, is almost panconnected except the path of length image for any two distinct vertices image. In this paper, we give a necessary and sufficient condition to check for the existence of paths of length image, called the nearly shortest paths, for any two distinct vertices image in image. 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.