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   Vol.E85-A   No.6   pp.1359-1370
Publication Date: 2002/06/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
crossed cube,  fault tolerant,  Hamiltonian,  Hamiltonian connected,  

Full Text: PDF>>
Buy this Article

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.