One-to-one node disjoint paths on divide-and-swap cubes

Abstract

In massive parallel and distributed systems, high fault-tolerance and reliability are extremely important for interconnection networks. Node-disjoint paths play a key role in improving the performance, reliability and scalability of networks.The hypercube, as well as many hypercube-like variants, are among the most popular and attractive network architectures. The divide-and-swap cube $\mathrm{DS}{C}_n$ is a newly proposed hypercube variant which has many desirable properties. In this work, we show that there exist d + 1 node-disjoint paths between any two distinct nodes in divide-and-swap cubes. Since the connectivity of the network is d + 1, d + 1 is the maximum number of paths that can be constructed between any two distinct nodes.

Keywords:

• Interconnection network
• multiprocessor system
• node-disjoint path
• divide-and-swap cube

2020 Mathematics Subject Classifications:

• 05C38
• 05C40

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The data used to support the findings of this study are available from the corresponding author upon request.

Additional information

Funding

This research was funded by the Research Project of Suzhou Industrial Park Institute of Services Outsourcing (No. SISO-ZD202202), the High-end Research Project of Teachers' Professional Leaders in Higher Vocational Colleges in Jiangsu Province (Nos. 2024GRFX040, 2024GRFX039) and the Qinglan Project of Jiangsu Province.