For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On the Fault-Tolerant Hamiltonicity of Faulty Crossed Cubes
Wen-Tzeng HUANG Yen-Chu CHUANG Jimmy Jiann-Mean TAN Lih-Hsing HSU
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2002/06/01
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
crossed cube, fault tolerant, Hamiltonian, Hamiltonian connected,
Full Text: PDF>>
An n-dimensional crossed cube, CQn, is a variation of the hypercube. In this paper, we prove that CQn is (n-2)-Hamiltonian and (n-3)-Hamiltonian connected. That is, a ring of length 2n-fv can be embedded in a faulty CQn with fv faulty nodes and fe faulty edges, where fv+fen-2 and n3. In other words, we show that the faulty CQn 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 CQn with n-3 faults. The above results are optimum in the sense that the fault-tolerant Hamiltonicity (fault-tolerant Hamiltonian connectivity respectively) of CQn is at most n-2 (n-3 respectively). A recent result has shown that a ring of length 2n-2fv can be embedded in a faulty hypercube, if fv+fen-1 and n4, with a few additional constraints. Our results, in comparison to the hypercube, show that longer rings can be embedded in CQn without additional constraints.