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

arXiv2207.12636MaRDI QIDQ6406053FDOQ6406053

Authors: Ningning Song, Yuxing Yang 

Publication date: 25 July 2022

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 $nin1,2$. Assume it holds for $n-1$ and prove it holds for $n$, where $ngeq3$. 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.

Mathematics Subject Classification ID

Paths and cycles (05C38)

This page was built for publication: Optimal edge fault-tolerant-prescribed hamiltonian laceability of balanced hypercubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6406053)