A note on fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges

被引：0
|
作者：
Tz-Liang Kueng
Cheng-Kuan Lin
Tyne Liang
Jimmy J. M. Tan
Lih-Hsing Hsu
机构：
[1] National Chiao Tung University,Department of Computer Science
[2] Providence University,Department of Computer Science and Information Engineering
来源：
Journal of Combinatorial Optimization | 2009年 / 17卷
关键词：
Interconnection network; Hypercube; Fault tolerance; Hamiltonian cycle;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In the paper “Fault-free Mutually Independent Hamiltonian Cycles in Hypercubes with Faulty Edges” (J. Comb. Optim. 13:153–162, 2007), the authors claimed that an n-dimensional hypercube can be embedded with (n−1−f)-mutually independent Hamiltonian cycles when f≤n−2 faulty edges may occur accidentally. However, there are two mistakes in their proof. In this paper, we give examples to explain why the proof is deficient. Then we present a correct proof.
引用
收藏
页码：312 / 322
页数：10
相关论文
共 50 条
  • [1] A note on fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges
    Kueng, Tz-Liang
    Lin, Cheng-Kuan
    Liang, Tyne
    Tan, Jimmy J. M.
    Hsu, Lih-Hsing
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 17 (03) : 312 - 322
  • [2] On the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty hypercube
    Kung, Tzu-Liang
    Lin, Cheng-Kuan
    Hsu, Lih-Hsing
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2014, 27 (02) : 328 - 344
  • [3] On the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty hypercube
    Tzu-Liang Kung
    Cheng-Kuan Lin
    Lih-Hsing Hsu
    Journal of Combinatorial Optimization, 2014, 27 : 328 - 344
  • [4] Fault-free mutually independent Hamiltonian cycles of faulty star graphs
    Kung, Tzu-Liang
    Lin, Cheng-Kuan
    Liang, Tyne
    Tan, Jimmy J. M.
    Hsu, Lih-Hsing
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2011, 88 (04) : 731 - 746
  • [5] On the mutually independent Hamiltonian cycles in faulty hypercubes
    Vukasinovic, Vida
    Gregor, Petr
    Skrekovski, Riste
    INFORMATION SCIENCES, 2013, 236 : 224 - 235
  • [6] Fault-free Hamiltonian cycle including given edges in folded hypercubes with faulty edges
    Cheng, Dongqin
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2020, 12 (03)
  • [7] Matchings extend to Hamiltonian cycles in hypercubes with faulty edges
    Xie-Bin Chen
    Frontiers of Mathematics in China, 2019, 14 : 1117 - 1132
  • [8] Matchings extend to Hamiltonian cycles in hypercubes with faulty edges
    Chen, Xie-Bin
    FRONTIERS OF MATHEMATICS IN CHINA, 2019, 14 (06) : 1117 - 1132
  • [9] Hamiltonian cycles in hypercubes With faulty edges
    Liu, Jia-Jie
    Wang, Yue-Li
    INFORMATION SCIENCES, 2014, 256 : 225 - 233
  • [10] Fault-free cycles in folded hypercubes with more faulty elements
    Fu, Jung-Sheng
    INFORMATION PROCESSING LETTERS, 2008, 108 (05) : 261 - 263
12345