The bi-panconnectivity of the hypercube

摘要

A bipartite graph is bi-panconnected if an arbitrary pair of vertices x, y are connected by the bi-panconnected paths that include a path of each length s satisfying N-1 ges s ges dist(x, y) and s-dist(x, y) is even, where N is the number of vertices, and dist(x, y) denotes the shortest distance between x and y. Li et al. [Information Processing Letters 87 (2003) 107-110] have shown that the hypercube is bi-panconnected. However, a definite algorithm to generate such paths is still absent. In this paper, we present algorithms to generate the bi-panconnected paths joining an arbitrary pair of vertices in the hypercube.