Fault-tolerant Hamiltonian laceability of balanced hypercubes

The balanced hypercube, as a new variant of hypercube, has many desirable properties such as strong connectivity, high regularity and symmetry. The particular property of the balanced hypercube is that each processor has a backup processor sharing the same neighborhood. A Hamiltonian bipartite graph G=(V0∪V1,E)G=(V0∪V1,E) is said to be Hamiltonian laceable if there is a Hamiltonian path between any two vertices x∈V0x∈V0 and y∈V1y∈V1. It has been proved that the balanced hypercube BHnBHn is Hamiltonian laceable for all n⩾1n⩾1. In this paper, we have proved that after at most 2n-22n-2 faulty edges occur, BHnBHn remains Hamiltonian laceable for all n⩾2n⩾2, this result is optimal with respect to the number of faulty edges can be tolerated in BHnBHn.