Fault-free Hamiltonian paths passing through prescribed linear forests in balanced hypercubes with faulty links

The n-dimensional balanced hypercube BHn is one of candidate interconnection networks for multiprocessor systems, and it is a bipartite graph. Let F be a set of faulty links and L be a fault-free linear forest in BHn. For any two nodes u and v in different parts of BHn such that none of the paths in L has u or v as internal node or both of them as end nodes, we prove that BHn admits a fault-free hamiltonian path between u and v passing through L even if the total number of links in F and L is up to 2n - 2. The upper bound on the number of links in F and L is optimal. This generalizes some known results.(c) 2022 Elsevier B.V. All rights reserved.

Automated summary

This article introduces the n-dimensional balanced hypercube BHn as a candidate interconnection network for multiprocessor systems, and proves that under certain conditions, BHn can achieve fault-free Hamiltonian paths between nodes.