Constructing the nearly shortest path in crossed cubes

A graph G is panconnected if each pair of distinct vertices u, v is an element of V(G) are joined by a path of length l for all d(G)(u, v) <= l <= 1.2 V(G)vertical bar - 1, where d(G)(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 Mobius Cubes and crossed cubes, Inform. Proc. Lett. 97 (3) (2006) 94-97] both proved that n-dimensional crossed cube, CQ(n), is almost panconnected except the path of length d(CQn)(u, v) + 1 for any two distinct vertices u, v is an element of V(CQ(n)). In this paper, we give a necessary and sufficient condition to check for the existence of paths of length d(CQn)(u, v) + 1, called the nearly shortest paths, for any two distinct vertices u, v in CQ(n). 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. (C) 2009 Elsevier Inc. All rights reserved.