A topological property of hypercubes: node disjoint paths

A graph G=(V,E) (|V|⩾2n) satisfies property P_n if given any 2n distinct vertices s₁,s ₂, . . ., s_n, g₁,g₂, . . ., g_n ∈V, there exist n node disjoint paths p _i[s_i, g_i] (i =1, . . ., n) in G such that p_i is a path from s_i to g_i. A necessary (but not sufficient) condition for any graph to satisfy P_n is that it be (2n-1)-connected [MW]. The authors prove the optimal result that the hypercube of dimension k , Q(k) (k⩾2n-1), satisfies P_n(n⩾3). The proof is constructive and yields an O(n³ log n) algorithm for finding up to [n/2] node disjoint paths in Q(n ) (n⩾4) between mutually disjoint source-goal node pairs