Edge-Disjoint Hamiltonian Cycles in Balanced Hypercubes with Applications to Fault-Tolerant Data Broadcasting
Shuai Liu, Yan Wang, Jianxi Fan, Baolei Cheng · International Journal of Foundations of Computer Science · 2024
The existence of multiple edge-disjoint Hamiltonian cycles (EDHCs for short) is a desirable property of interconnection networks. These parallel cycles can provide an advantage for algorithms that require a ring structure. Additionally, EDHCs can enhance all-to-all data broadcasting and edge fault tolerance in network communications. In this paper, we investigate the construction of EDHCs in the balanced hypercube, which is a variant of the hypercube with many attractive properties, such as strong connectivity, regularity, and symmetry. In particular, each processor in the balanced hypercube has a backup processor that shares the common neighbors, enabling fault tolerance and efficient system reconfiguration. In 2019, Lü et al. provided an algorithm to construct two EDHCs in an [Formula: see text]-dimensional balanced hypercube [Formula: see text] for [Formula: see text]. We further study this topic and give some construction schemes to construct [Formula: see text] EDHCs in [Formula: see text] for [Formula: see text]. Since [Formula: see text] is [Formula: see text]-regular, our result is optimal for [Formula: see text] ([Formula: see text]). In addition, we simulate the fault-tolerant data broadcasting through these parallel cycles as transmission channels.