Optimal edge fault-tolerant-prescribed hamiltonian laceability of balanced hypercubes

2022/07/26 by Ningning Song, Song, Ningning, Yuxing Yang +1
Computer Science · Engineering · #05C38 #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Satellite Communication Systems #Software-Defined Networks and 5G

paper · pdf · doi:10.48550/arxiv.2207.12636

openalex publication_date 2022/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Aims: Try to prove the n-dimensional balanced hypercube BH_n is (2n-2)-fault-tolerant-prescribed hamiltonian laceability. Methods: Prove it by induction on n. It is known that the assertation holds for n∈\1,2\. Assume it holds for n-1 and prove it holds for n, where n≥ 3. If there are 2n-3 faulty links and they are all incident with a common node, then we choose some dimension such that there is one or two faulty links and no prescribed link in this dimension; Otherwise, we choose some dimension such that the total number of faulty links and prescribed links does not exceed 1. No matter which case, partition BH_n into 4 disjoint copies of BH_n-1 along the above chosen dimension. Results: On the basis of the above partition of BH_n, in this manuscript, we complete the proof for the case that there is at most one faulty link in the above chosen dimension.

Related

• Fault-tolerance of balanced hypercubes with faulty vertices and faulty edges
• Fault-free Hamiltonian cycles in balanced hypercube with conditional edge faults
• Hamiltonian laceability with a set of faulty edges in hypercubes
• Paired many-to-many 2-disjoint path cover of balanced hypercubes with faulty edges
• Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges