A note on cycle embedding in hypercubes with faulty vertices

被引：14
作者：
Du, Zheng-Zhong [1 ]
Xu, Jun-Ming [1 ]
机构：
[1] Univ Sci & Technol China, Dept Math, Hefei 230026, Anhui, Peoples R China
来源：
INFORMATION PROCESSING LETTERS | 2011年 / 111卷 / 12期
关键词：
Combinatorics; Cycle; Graph; Hypercube; Fault tolerance; HAMILTONIAN-LACEABILITY; PATH; BIPANCONNECTIVITY; BIPANCYCLICITY; RING; NODES;
D O I：
10.1016/j.ipl.2011.03.002
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Let f(v) denote the number of faulty vertices in an n-dimensional hypercube. This note shows that a fault-free cycle of length of at least 2(n) - 2f(v) can be embedded in an n-dimensional hypercube with f(v) = 2n - 3 and n >= 5. This result not only enhances the previously best known result, and also answers a question in [J.-S. Fu, Fault-tolerant cycle embedding in the hypercube, Parallel Computing 29 (2003) 821-832]. (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码：557 / 560
页数：4
相关论文
共 29 条
[1]  
Akl S.G., 1997, Parallel Computation: Models and Methods
[2]  
[Anonymous], SIAM J DISCRETE MATH
[3]   Cycles passing through prescribed edges in a hypercube with some faulty edges [J].
Chen, Xie-Bin .
INFORMATION PROCESSING LETTERS, 2007, 104 (06) :211-215
[4]   Edge-fault-tolerant diameter and bipanconnectivity of hypercubes [J].
Chen, Xie-Bin .
INFORMATION PROCESSING LETTERS, 2010, 110 (24) :1088-1092
[5]   Cycles passing through a prescribed path in a hypercube with faulty edges [J].
Chen, Xie-Bin .
INFORMATION PROCESSING LETTERS, 2010, 110 (16) :625-629
[6]   Hamiltonian paths and cycles passing through a prescribed path in hypercubes [J].
Chen, Xie-Bin .
INFORMATION PROCESSING LETTERS, 2009, 110 (02) :77-82
[7]   Many-to-many disjoint paths in faulty hypercubes [J].
Chen, Xie-Bin .
INFORMATION SCIENCES, 2009, 179 (18) :3110-3115
[8]   On path bipancyclicity of hypercubes [J].
Chen, Xie-Bin .
INFORMATION PROCESSING LETTERS, 2009, 109 (12) :594-598
[9]   Fault-tolerant cycle embedding in the hypercube [J].
Fu, JS .
PARALLEL COMPUTING, 2003, 29 (06) :821-832
[10]   EDGE FAULT TOLERANCE IN GRAPHS [J].
HARARY, F ;
HAYES, JP .
NETWORKS, 1993, 23 (02) :135-142
123