標題: Edge-bipancyclicity of conditional faulty hypercubes
作者: Shih, Lun-Min
Tan, Jimmy J. M.
Hsu, Lih-Hsing
資訊工程學系
Department of Computer Science
關鍵字: cycles;pancyclic;conditional fault;hypercube;fault-tolerant;interconnection networks
公開日期: 31-十二月-2007
摘要: Xu et al. showed that for any set of faulty edges F of an n-dimensional hypercube Q(n) with vertical bar F vertical bar <= n - 1, each edge of Q(n) - F lies on a cycle of every even length from 6 to 2(n), n >= 4, provided not all edges in F are incident with the same vertex. In this paper, we find that under similar condition, the number of faulty edges can be much greater and the same result still holds. More precisely, we show that, for up to vertical bar F vertical bar = 2n - 5 faulty edges, each edge of the faulty hypercube Q(n) - F lies on a cycle of every even length from 6 to 2(n) with each vertex having at least two healthy edges adjacent to it, for n >= 3. Moreover, this result is optimal in the sense that there is a set F of 2n - 4 conditional faulty edges in Q(n) such that Q(n) - F contains no hamiltonian cycle. (c) 2007 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.ipl.2007.07.009
http://hdl.handle.net/11536/9993
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2007.07.009
期刊: INFORMATION PROCESSING LETTERS
Volume: 105
Issue: 1
起始頁: 20
結束頁: 25
顯示於類別:期刊論文


文件中的檔案:

  1. 000250693100005.pdf