On the fault-tolerant Hamiltonicity of faulty crossed cubes

Abstract

An n-dimensional crossed cube, CQ(n), is a variation of the hypercube. In this paper, we prove that CQ(n) is (n-2)-Hamiltonian and (n-3)-Hamiltonian connected. That is, a ring of length 2(n)-f(v) can be embedded in a faulty CQ(n) with f(v) faulty nodes and f(e) faulty edges, where f(v)+f(e) less than or equal to n-2 and n greater than or equal to 3. In other words, we show that the faulty CQ(n) is still Hamiltonian with n-2 faults. In addition, we also prove that there exists a Hamiltonian path between any pair of vertices in a faulty CQ(n) with n-3 faults. The above results are optimum in the sense that the fault-tolerant Hamiltonicity (fault-tolerant Hamiltonian connectivity respectively) Of CQ(n) is at most n-2 (n-3 respectively). A recent result has shown that a ring of length 2(n)-2f(v) can be embedded in a faulty hypercube, if f(v)+f(e) less than or equal to n-1 and n greater than or equal to 4, with a few additional constraints [17]. Our results, in comparison to the hypercube, show that longer rings can be embedded in CQ(n) without additional constraints.