Unpaired Many-to-Many Disjoint Path Cover of Balanced Hypercubest.

A many-to-many k -disjoint path cover (k -DPC) of a graph G is a set of k vertex-disjoint paths joining k distinct pairs of source and sink in which each vertex of G is contained exactly once in a path. The balanced hypercube B H n , a variant of the hypercube, was introduced as a desired interconnection network topology. Let S = { s 1 , s 2 , ... , s 2 n − 2 } and T = { t 1 , t 2 , ... , t 2 n − 2 } be any two sets of vertices in different partite sets of B H n (n ≥ 2). Cheng et al. in [Appl. Math. Comput. 242 (2014) 127–142] proved that there exists paired many-to-many 2-disjoint path cover of B H n when | S | = | T | = 2. In this paper, we prove that there exists unpaired many-to-many (2 n − 2) -disjoint path cover of B H n (n ≥ 2) from S to T , which has improved some known results. The upper bound 2 n − 2 is best possible in terms of the number of disjoint paths in unpaired many-to-many k -DPC of B H n . [ABSTRACT FROM AUTHOR]