The 2-path-bipanconnectivity of hypercubes

In this paper, we introduce the concept of the k-path-(bi)panconnectivity of (bipartite) graphs. It is a generalization of the (bi)panconnectivity and of the paired many-to-many k-disjoint path cover. The 2-path-bipanconnectivity with only one exception of the n-cube Q(n) (n >= 4) is proved. Precisely, the following result is obtained: In an n-cube with n >= 4 given any four vertices u(1), v(1), u(2), v(2) such that two of them are in one partite set and the another two are in the another partite set. Let s = t = 5 if C = u(1)u(2)v(1)v(2) is a cycle of length 4, and s = d(u(1), v(1)) + 1 and t = d(u(2), v(2)) + 1 otherwise, where d(u, v) denotes the distance between two vertices u and v. And let i and j be any two integers such that both i - s >= 0 and j - t >= 0 are even with i + j <= 2(n). Then there exist two vertex-disjoint (u(1), v(1))-path P and (u(2), v(2))-path R with vertical bar V(P)vertical bar = i and vertical bar V(R)vertical bar = j. As consequences, many properties of hypercubes, such as bipanconnectivity, bipanpositionable bipanconnectivity [18], bipancycle-connectivity [12], two internally disjoint paths with two given lengths, and the 2-disjoint path cover with a path of a given length [21], follow from our result. (C) 2013 Elsevier Inc. All rights reserved.