Optimizing Hamiltonian panconnectedness for the crossed cube architecture

摘要

A graph G of k vertices is panconnected if for any two distinct vertices x and y, it has a path of length l joining x and y for any integer l satisfying dG(x,y)≤l≤k−1, where dG(x, y) denotes the distance between x and y in G. In particular, when k ≥ 3, G is called Hamiltonian r-panconnected if for any three distinct vertices x, y, and z, there exists a Hamiltonian path P of G with dP(x,y)=l such that P(1)=x, P(l+1)=y, and P(k)=z for any integer l satisfying r≤l≤k−r−1, where P(i) denotes the ith vertex of path P for 1 ≤ i ≤ k. Then, this paper shows that the n-dimensional crossed cube, which is a popular variant of the hypercube topology, is Hamiltonian (⌈n+12⌉+1)-panconnected for n ≥ 4. The lower bound ⌈n+12⌉+1 on the path length is sharp, which is the shortest that can be embedded between any two distinct vertices with dilation 1 in the n-dimensional crossed cube.