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 条

[11] Hamiltonian cycles and paths in hypercubes with disjoint faulty edges
Dybizbanski, Janusz
Szepietowski, Andrzej
INFORMATION PROCESSING LETTERS, 2021, 172 (172)
[12] Fault-free cycles passing through prescribed a linear forest in a hypercube with faulty edges
Yao, Xiao-Pan
Chen, Xie-Bin
ARS COMBINATORIA, 2014, 116 : 213 - 223
[13] Fault-free Hamiltonian cycles in faulty arrangement graphs
Hsieh, SY
Chen, GH
Ho, CW
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1999, 10 (03) : 223 - 237
[14] A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges
Wang, Wen-Qing
Chen, Xie-Bin
INFORMATION PROCESSING LETTERS, 2008, 107 (06) : 205 - 210
[15] Mutually independent hamiltonian cycles in hypercubes
Sun, CM
Lin, CK
Huang, HM
Hsu, LH
8th International Symposium on Parallel Architectures, Algorithms and Networks, Proceedings, 2005, : 504 - 509
[16] Hamiltonian cycles in hypercubes with 2n-4 faulty edges
Szepietowski, Andrzej
INFORMATION SCIENCES, 2012, 215 : 75 - 82
[17] Fault-tolerant cycles embedding in hypercubes with faulty edges
Cheng, Dongqin
Hao, Rong-Xia
INFORMATION SCIENCES, 2014, 282 : 57 - 69
[18] Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges
Wang, Fan
Zhang, Heping
DISCRETE MATHEMATICS, 2014, 321 : 35 - 44
[19] Fault-Free Hamiltonian Cycles in Balanced Hypercubes with Conditional Edge Faults
Li, Pingshan
Xu, Min
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2019, 30 (05) : 693 - 717
[20] Fault-free Hamiltonian cycles passing through a prescribed linear forest in 3-ary n-cube with faulty edges
Chen, Xie-Bin
FRONTIERS OF MATHEMATICS IN CHINA, 2014, 9 (01) : 17 - 30

← 1 2 3 4 5 →