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 条
  • [21] Long cycles in hypercubes with optimal number of faulty vertices
    Jiří Fink
    Petr Gregor
    Journal of Combinatorial Optimization, 2012, 24 : 240 - 265
  • [22] On ring embedding in hypercubes with faulty nodes and links
    Sengupta, A
    INFORMATION PROCESSING LETTERS, 1998, 68 (04) : 207 - 214
  • [23] Embedding and reconfiguration of spanning trees in faulty hypercubes
    Avresky, DR
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1999, 10 (03) : 211 - 222
  • [24] Various cycles embedding in faulty balanced hypercubes
    Cheng, Dongqin
    Hao, Rong-Xia
    INFORMATION SCIENCES, 2015, 297 : 140 - 153
  • [25] Embedding general spanning trees in faulty hypercubes
    Avresky, DR
    Altawil, KM
    COMPUTER SYSTEMS SCIENCE AND ENGINEERING, 1999, 14 (03): : 167 - 174
  • [26] CYCLES EMBEDDING ON FOLDED HYPERCUBES WITH FAULTY NODES
    Dan Yuan
    Hongmei Liu
    Maozheng Tang
    AnnalsofAppliedMathematics, 2016, 32 (01) : 69 - 78
  • [27] EMBEDDING CUBE-CONNECTED CYCLES GRAPHS INTO FAULTY HYPERCUBES
    BRUCK, J
    CYPHER, R
    SOROKER, D
    IEEE TRANSACTIONS ON COMPUTERS, 1994, 43 (10) : 1210 - 1220
  • [28] Hamiltonian Cycle Embeddings in Faulty Hypercubes Under the Forbidden Faulty Set Model
    Li, Chunfang
    Lin, Shangwei
    Li, Shengjia
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2021, 32 (01) : 53 - 72
  • [29] Disjoint cycles in hypercubes with prescribed vertices in each cycle
    Lin, Cheng-Kuan
    Tan, Jimmy J. M.
    Hsu, Lih-Hsing
    Kung, Tzu-Liang
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (18) : 2992 - 3004
  • [30] EMBEDDING OF RINGS AND MESHES ONTO FAULTY HYPERCUBES USING FREE DIMENSIONS
    YANG, PJ
    TIEN, SB
    RAGHAVENDRA, CS
    IEEE TRANSACTIONS ON COMPUTERS, 1994, 43 (05) : 608 - 613
12345