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
相关论文
共 50 条
  • [1] A note on cycle embedding in folded hypercubes with faulty elements
    Hsieh, Sun-Yuan
    INFORMATION PROCESSING LETTERS, 2008, 108 (02) : 81 - 81
  • [2] 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)
  • [3] Hamiltonicity of hypercubes with faulty vertices
    Chen, Xie-Bin
    INFORMATION PROCESSING LETTERS, 2016, 116 (05) : 343 - 346
  • [4] Cycles embedding in folded hypercubes with conditionally faulty vertices
    Kuo, Che-Nan
    Cheng, Yu-Huei
    DISCRETE APPLIED MATHEMATICS, 2017, 220 : 55 - 59
  • [5] Path embedding in faulty hypercubes
    Ma, Meijie
    Liu, Guizhen
    Pan, Xiangfeng
    APPLIED MATHEMATICS AND COMPUTATION, 2007, 192 (01) : 233 - 238
  • [6] Long paths and cycles in hypercubes with faulty vertices
    Fink, Jiri
    Gregor, Petr
    INFORMATION SCIENCES, 2009, 179 (20) : 3634 - 3644
  • [7] Extended Fault-Tolerant Cycle Embedding in Faulty Hypercubes
    Hsieh, Sun-Yuan
    Chang, Nai-Wen
    IEEE TRANSACTIONS ON RELIABILITY, 2009, 58 (04) : 702 - 710
  • [8] Fault-tolerant cycle embedding in the faulty hypercubes
    Cheng, Dongqin
    Guo, Dachang
    INFORMATION SCIENCES, 2013, 253 : 157 - 162
  • [9] Fault-tolerant cycles embedding in hypercubes with faulty edges
    Cheng, Dongqin
    Hao, Rong-Xia
    INFORMATION SCIENCES, 2014, 282 : 57 - 69
  • [10] A note on path embedding in crossed cubes with faulty vertices
    Chen, Hon -Chan
    Zou, Yun-Hao
    Wang, Yue-Li
    Pai, Kung-Jui
    INFORMATION PROCESSING LETTERS, 2017, 121 : 34 - 38
12345