Unpaired Many-to-Many Disjoint Path Cover of Balanced Hypercubes

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 BHn, a variant of the hypercube, was introduced as a desired interconnection network topology. Let S = {s(1), s(2), ... s(2n-2)} and T = {t(1), t(2), ..., t(2n-2)} be any two sets of vertices in different partite sets of BHn (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 BHn when vertical bar S vertical bar = vertical bar T vertical bar = 2. In this paper, we prove that there exists unpaired many-to-many (2n-2)-disjoint path cover of BHn (n >= 2) from S to T, which has improved some known results. The upper bound 2n-2 is best possible in terms of the number of disjoint paths in unpaired many-to-many k-DPC of BHn.

Automated summary

This paper discusses the many-to-many k-disjoint path cover of a graph G and the balanced hypercube BHn, proving the existence of an unpaired many-to-many (2n-2)-disjoint path cover in BHn, while also improving existing results. The upper bound of 2n-2 is proven to be the best possible in terms of the number of disjoint paths in unpaired many-to-many k-DPC of BHn.