Algorithmic bipanpath connectivity of the hypercube

摘要

A bipartite graph is bipanconnected if an arbitrary pair of vertices x, y are joined by the bipanconnected paths that include a path of each length s satisfying N - 1 ≥ s ≥ dist(x, y) and s - dist(x, y) is even, where N is the order of the graph, 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 bipanconnected. However, a definite algorithm to generate such paths is still absent. In this paper, we present algorithms to generate the bipanconnected paths joining an arbitrary pair of vertices in the hypercube.