Hamiltonian laceability with a set of faulty edges in hypercubes

2025/06/26 by Ali, Abid, Yang, Weihua
#05C45 #05C70 #Combinatorics (math.CO) #F.2.2 #FOS: Mathematics

paper · doi:10.48550/arxiv.2506.21391

Abstract

Faulty networks are useful because link or node faults can occur in a network. This paper examines the Hamiltonian properties of hypercubes under certain conditional faulty edges. Let consider the hypercube \( Q_n \), for \( n ≥ 5 \) and set of faulty edges \( F \) such that \( |F| ≤ 4n - 17 \). We prove that a Hamiltonian path exists connecting any two vertices in \( Q_n - F \) from distinct partite sets if they verify the next two conditions: (i) in Q_n - F any vertex has a degree at least 2, and (ii) in Q_n - F at most one vertex has a degree exactly equal to 2. These findings provide an understanding of fault-tolerant properties in hypercube networks.

Related

• Hamiltonian Connectivity of Twisted Hypercube-Like Networks under the Large Fault Model
• Fault-tolerance of balanced hypercubes with faulty vertices and faulty edges
• Optimal edge fault-tolerant-prescribed hamiltonian laceability of balanced hypercubes
• Fault-free Hamiltonian cycles in balanced hypercube with conditional edge faults
• Edge-Fault Tolerance of Hypercube-like Networks