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 条

[21] Fault-free Hamiltonian cycles passing through a prescribed linear forest in 3-ary n-cube with faulty edges
Xie-Bin Chen
Frontiers of Mathematics in China, 2014, 9 : 17 - 30
[22] Fault-Free Hamiltonian Cycles Passing through Prescribed Edges in k-Ary n-Cubes with Faulty Edges
Zhang, Shurong
Zhang, Xianwen
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2015, 26 (02) : 434 - 443
[23] Fault-free Hamiltonian cycles passing through a linear forest in ternary n-cubes with faulty edges
Yang, Yuxing
Wang, Shiying
THEORETICAL COMPUTER SCIENCE, 2013, 491 : 78 - 82
[24] Fault-free Hamiltonian paths passing through prescribed linear forests in balanced hypercubes with faulty links
Yang, Yuxing
Song, Ningning
THEORETICAL COMPUTER SCIENCE, 2023, 939 : 161 - 169
[25] Embedding a fault-free hamiltonian cycle in a class of faulty generalized honeycomb tori
Dong, Qiang
Yang, Xiaofan
Zhao, Juan
COMPUTERS & ELECTRICAL ENGINEERING, 2009, 35 (06) : 942 - 950
[26] Small matchings extend to Hamiltonian cycles in hypercubes with disjoint faulty edges
Wang, Fan
DISCRETE APPLIED MATHEMATICS, 2025, 363 : 16 - 26
[27] Hamiltonian laceability in hypercubes with faulty edges
Wang, Fan
Zhang, Heping
DISCRETE APPLIED MATHEMATICS, 2018, 236 : 438 - 445
[28] Fault-free Hamiltonian cycles in twisted cubes with conditional link faults
Fu, Jung-Sheng
THEORETICAL COMPUTER SCIENCE, 2008, 407 (1-3) : 318 - 329
[29] Fault-free Hamiltonian cycles in crossed cubes with conditional link faults
Hung, Hao-Shun
Fu, Jung-Sheng
Chen, Gen-Huey
INFORMATION SCIENCES, 2007, 177 (24) : 5664 - 5674
[30] Hamiltonian cycles of balanced hypercube with more faulty edges
Lan, Ting
Lu, Huazhong
THEORETICAL COMPUTER SCIENCE, 2023, 947

← 1 2 3 4 5 →