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 条

[31] 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
[32] Conditional fault-tolerant edge-bipancyclicity of hypercubes with faulty vertices and edges
Yang, Da-Wei
Gu, Mei-Mei
THEORETICAL COMPUTER SCIENCE, 2016, 627 : 82 - 89
[33] Embedding even cycles on folded hypercubes with conditional faulty edges
Cheng, Dongqin
Hao, Rong-Xia
Feng, Yan-Quan
INFORMATION PROCESSING LETTERS, 2015, 115 (12) : 945 - 949
[34] Bipanconnectivity of faulty hypercubes with minimum degree
Sun, Chao-Ming
APPLIED MATHEMATICS AND COMPUTATION, 2012, 218 (09) : 5518 - 5523
[35] Hamiltonian cycle embedding for fault tolerance in balanced hypercubes
Hao, Rong-Xia
Zhang, Ru
Feng, Yan-Quan
Zhou, Jin-Xin
APPLIED MATHEMATICS AND COMPUTATION, 2014, 244 : 447 - 456
[36] Every edge lies on cycles of folded hypercubes with a pair of faulty adjacent vertices
Kuo, Che-Nan
Cheng, Yu-Huei
DISCRETE APPLIED MATHEMATICS, 2021, 294 : 1 - 9
[37] Cycles in highly faulty hypercubes
Yang, MC
Tan, JJM
Hsu, LH
FCS '05: Proceedings of the 2005 International Conference on Foundations of Computer Science, 2005, : 101 - 107
[38] Paired many-to-many disjoint path covers in faulty hypercubes
Jo, Shinhaeng
Park, Jung-Heum
Chwa, Kyung-Yong
THEORETICAL COMPUTER SCIENCE, 2013, 513 : 1 - 24
[39] A note on fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges
Kueng, Tz-Liang
Lin, Cheng-Kuan
Liang, Tyne
Tan, Jimmy J. M.
Hsu, Lih-Hsing
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 17 (03) : 312 - 322
[40] A note on fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges
Tz-Liang Kueng
Cheng-Kuan Lin
Tyne Liang
Jimmy J. M. Tan
Lih-Hsing Hsu
Journal of Combinatorial Optimization, 2009, 17 : 312 - 322

← 1 2 3 4 5 →