標題: On the fault-tolerant Hamiltonicity of faulty crossed cubes
作者: Huang, WT
Chuang, YC
Tan, JJM
Hsu, LH
資訊工程學系
Department of Computer Science
關鍵字: crossed cube;fault-tolerant;Hamiltonian;Hamiltonian connected
公開日期: 1-Jun-2002
摘要: 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.
URI: http://hdl.handle.net/11536/28730
ISSN: 0916-8508
期刊: IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
Volume: E85A
Issue: 6
起始頁: 1359
結束頁: 1370
Appears in Collections:Articles