On the Spanning Laceability of Multi-Dimensional Torus Networks

One-to-one disjoint path routing constitutes an essential traffic model in which one server may transmit data packets to another server via several internally vertex-disjoint paths. It has been thoroughly investigated because it benefits fault-tolerant ability, load balancing, and congestion control. A bipartite graph H with bipartition V0 and V1 is k∗-laceable if for any u∈V0 and v∈V1, there exist k internally vertex-disjoint paths between u and v whose union covers all vertices of H. Let u be a vertex of G, and let S={v1,v2,…,vk} be a subset of V(G)∖{u}. A spanning (u,S)-fan is a set of internally vertex-disjoint paths {P1,P2,…,Pk} in G such that Pi connects u to vi for each 1≤i≤k, and ⋃i=1kV(Pi)=V(G). The multi-dimensional torus network, as a natural generalization of the hypercube, is a widely studied network with a high degree of symmetry. This paper shows that a bipartite torus admits a spanning (u,S)-fan, by which it follows that an n-dimensional bipartite torus T(d1,d2,…,dn) is k∗-laceable for every 1≤k≤2n. The result is optimal with respect to the degree of the torus.