On the Fault-Tolerant Hamiltonicity of Faulty Crossed Cubes

概要

論文の詳細を見る
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 he embedded in a faulty CQ_n with f_v faulty nodes and f_e faulty edges, where f_v+f_e ≤ n - 2 and n ≥ 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 ≤ n - 1 and n ≥ 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.
社団法人電子情報通信学会の論文
2002-06-01