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 条

[31] Embedding hamiltonian cycles into folded hypercubes with faulty links
Wang, DJ
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2001, 61 (04) : 545 - 564
[32] Fault-tolerance of balanced hypercubes with faulty vertices and faulty edges
Gu, Mei-Mei
Hao, Rong-Xia
ARS COMBINATORIA, 2018, 140 : 45 - 61
[33] Hamiltonian cycles with prescribed edges in hypercubes
Dvorák, T
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2005, 19 (01) : 135 - 144
[34] Novel schemes for embedding Hamiltonian paths and cycles in balanced hypercubes with exponential faulty edges
Li, Xiao-Yan
Zhao, Kun
Zhuang, Hongbin
Jia, Xiaohua
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2023, 177 : 182 - 191
[35] Fault-Free Vertex-Pancyclicity in Twisted Cubes with Faulty Edges
Fu, Jung-Sheng
INTERNATIONAL MULTICONFERENCE OF ENGINEERS AND COMPUTER SCIENTISTS (IMECS 2010), VOLS I-III, 2010, : 430 - 435
[36] Hamiltonian cycles and paths in faulty twisted hypercubes
Liu, Huiqing
Hu, Xiaolan
Gao, Shan
DISCRETE APPLIED MATHEMATICS, 2019, 257 : 243 - 249
[37] Odd cycles embedding on folded hypercubes with conditional faulty edges
Cheng, Dongqin
Hao, Rong-Xia
Feng, Yan-Quan
INFORMATION SCIENCES, 2014, 282 : 180 - 189
[38] Hamiltonian cycles of balanced hypercube with disjoint faulty edges
Lan, Ting
Lu, Huazhong
INFORMATION PROCESSING LETTERS, 2025, 187
[39] Longest fault-free paths in hypercubes with vertex faults
Fu, JS
INFORMATION SCIENCES, 2006, 176 (07) : 759 - 771
[40] Fault-Tolerant Cycle Embedding in Balanced Hypercubes with Faulty Vertices and Faulty Edges
Gu, Mei-Mei
Hao, Rong-Xia
Feng, Yan-Quan
JOURNAL OF INTERCONNECTION NETWORKS, 2015, 15 (1-2)

← 1 2 3 4 5 →