Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs
Let W(n) denote any bipartite graph obtained by adding some edges to the n-dimensional hypercube Q(n) and let S and T be any two sets of k vertices in different partite sets of W(n) In this paper, we show that the graph W(n) has k vertex-disjoint (S, T)-paths containing all vertices of W(n) if and only if k = 2(n-1) or the graph W(n) - (S boolean OR T) has a perfect matching. Moreover, if the graph W(n) - (S boolean OR T) has a perfect matching M, then tile graph W(n) has k vertex-disjoint (S. T)-paths containing all vertices of W(n) and all edges in M. And some corollaries are given. (C) 2009 Elsevier B.V. All rights reserved.
vertex-disjoint paths hypercube matching hamiltonian path folded hypercube interconnection network