Fault-free Hamiltonian cycles in balanced hypercube with conditional edge faults

Abstract

The balanced hypercube, $B{H}_n$, is a variant of hypercube $Q_n$. Zhou et al. [Inform. Sci. 300 (2015) 20-27] proposed an interesting problem that whether there is a fault-free Hamiltonian cycle in $B{H}_n$ with each vertex incident to at least two fault-free edges. In this paper, we consider this problem and show that each fault-free edge lies on a fault-free Hamiltonian cycle in $B{H}_n$ after no more than $4n-5$ faulty edges occur if each vertex is incident with at least two fault-free edges for all $n\ge 2$. Our result is optimal with respect to the maximum number of tolerated edge faults.

arXiv admin note: text overlap with arXiv:1606.05152