Conditional edge-fault Hamiltonicity of augmented cubes

被引：49
作者：
Hsieh, Sun-Yuan [1 ]
Cian, Yi-Ru [1 ]
机构：
[1] Natl Cheng Kung Univ, Dept Comp Sci & Informat Engn, Tainan 70101, Taiwan
来源：
INFORMATION SCIENCES | 2010年 / 180卷 / 13期
关键词：
Augmented cubes; Fault-tolerant embedding; Graph-theoretic interconnection networks; Hamiltonian cycles; Hamiltonicity; STAR GRAPHS; LONG PATHS; DISJOINT PATHS; CYCLES; HYPERCUBES; LINK; CONNECTIVITY;
D O I：
10.1016/j.ins.2010.03.005
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The augmented cube is a variation of hypercubes, it possesses many superior properties. In this paper, we show that, for any n-dimensional augmented cube (n >= 3) with faulty edges up to 4n - 8 in which each vertex is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result is optimal with respect to the number of faulty edges tolerated. (C) 2010 Elsevier Inc. All rights reserved.
引用
收藏
页码：2596 / 2617
页数：22
相关论文
共 44 条
[21]   Fault-tolerant cycle embedding in the hypercube with more both faulty vertices and faulty edges [J].
Hsieh, SY .
PARALLEL COMPUTING, 2006, 32 (01) :84-91
[22]   Longest fault-free paths in star graphs with edge faults [J].
Hsieh, SY ;
Chen, GH ;
Ho, CW .
IEEE TRANSACTIONS ON COMPUTERS, 2001, 50 (09) :960-971
[23]   Embedding longest fault-free paths onto star graphs with more vertex faults [J].
Hsieh, SY .
THEORETICAL COMPUTER SCIENCE, 2005, 337 (1-3) :370-378
[24]   Fault-free Hamiltonian cycles in faulty arrangement graphs [J].
Hsieh, SY ;
Chen, GH ;
Ho, CW .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1999, 10 (03) :223-237
[25]   Longest fault-free paths in star graphs with vertex faults [J].
Hsieh, SY ;
Chen, GH ;
Ho, CW .
THEORETICAL COMPUTER SCIENCE, 2001, 262 (1-2) :215-227
[26]   SPECIAL ISSUE - INTERCONNECTION NETWORKS AND ALGORITHMS - INTRODUCTION [J].
HSU, DF .
NETWORKS, 1993, 23 (04) :211-213
[27]   Fault hamiltonicity of augmented cubes [J].
Hsu, HC ;
Chiang, LC ;
Tan, JJM ;
Hsu, LH .
PARALLEL COMPUTING, 2005, 31 (01) :131-145
[28]   Fault-free Hamiltonian cycles in crossed cubes with conditional link faults [J].
Hung, Hao-Shun ;
Fu, Jung-Sheng ;
Chen, Gen-Huey .
INFORMATION SCIENCES, 2007, 177 (24) :5664-5674
[29]   Long paths in hypercubes with conditional node-faults [J].
Kueng, Tz-Liang ;
Liang, Tyne ;
Hsu, Lih-Hsing ;
Tan, Jimmy J. M. .
INFORMATION SCIENCES, 2009, 179 (05) :667-681
[30]   Constructing the nearly shortest path in crossed cubes [J].
Lai, Pao-Lien ;
Hsu, Hong-Chun .
INFORMATION SCIENCES, 2009, 179 (14) :2487-2493
12345