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

Abstract

Aims: Try to prove the $n$-dimensional balanced hypercube $B{H}_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\in \{1,2\}$. Assume it holds for $n-1$ and prove it holds for $n$, where $n\ge 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 $B{H}_n$ into $4$ disjoint copies of $B{H}_{n-1}$ along the above chosen dimension. Results: On the basis of the above partition of $B{H}_n$, in this manuscript, we complete the proof for the case that there is at most one faulty link in the above chosen dimension.

51pages, 0 figure