Fault tolerance for Hamiltonian cycle of node expansion on hypercube

Abstract

In this paper, we construct the variant of hypercube X(Qn; fxb; xwg) with node expansion on one black node xb and one white node xw of hy- percube Qn = (Vb [ Vw;E). Let F = Fb [ Fw [ F0 be the faulty set of X(Qn; fxb; xwg) where Fb ½ Vb, Fw ½ Vw and F0 are disjoint sets. We show that X(Qn; fxb; xwg) ¡ F is Hamil- tonian if (1):jFbj = jFwj = 0; jF0j · n ¡ 2, (2):0 < jFbj = jFwj · dn 4 e¡1; jF0j · n¡1¡4jFbj, (3):0 · jFwj 6= jFbj · dn 4 e¡2; jF0j · n¡3¡4fmax, for fmax = maxfjFbj; jFwjg. We thus derive that X(Qn; xb; xw) is k-Hamiltonian for k = dn 4 e ¡ 2. We also investigate the fault tolerance for multi- spanning disjoint paths of complete graph Kn and hypercube Qn.