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 条

[41] Many-to-many disjoint paths in faulty hypercubes [J].

Chen, Xie-Bin .

INFORMATION SCIENCES, 2009, 179 (18) :3110-3115

[42] Hamiltonian cycles and paths in hypercubes with disjoint faulty edges [J].

Dybizbanski, Janusz ;

Szepietowski, Andrzej .

INFORMATION PROCESSING LETTERS, 2021, 172 (172)

[43] Embedding a ring in a hypercube with both faulty links and faulty nodes [J].

Tseng, YC .

INFORMATION PROCESSING LETTERS, 1996, 59 (04) :217-222

[44] Embedding longest fault-free paths in arrangement graphs with faulty vertices [J].

Lo, RS ;

Chen, GH .

NETWORKS, 2001, 37 (02) :84-93

[45] Novel schemes for embedding Hamiltonian paths and cycles in balanced hypercubes with exponential faulty edges [J].

Li, Xiao-Yan ;

Zhao, Kun ;

Zhuang, Hongbin ;

Jia, Xiaohua .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2023, 177 :182-191

[46] Path Embedding in a Faulty Folded Hypercube [J].

Fu, Jung-Sheng ;

Chung, Ping-Che .

INTERNATIONAL MULTICONFERENCE OF ENGINEERS AND COMPUTER SCIENTISTS, IMECS 2012, VOL I, 2012, :289-292

[47] All-to-all broadcasting in faulty hypercubes [J].

Park, S ;

Bose, B .

IEEE TRANSACTIONS ON COMPUTERS, 1997, 46 (07) :749-755

[48] PARTITIONS OF FAULTY HYPERCUBES INTO PATHS WITH PRESCRIBED ENDVERTICES [J].

Dvorak, Tomas ;

Gregor, Petr .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 22 (04) :1448-1461

[49] Cycle-embedding problem on faulty twisted cubes [J].

Yang, MC ;

Li, TK ;

Tan, JJM ;

Hsu, LH .

8TH WORLD MULTI-CONFERENCE ON SYSTEMICS, CYBERNETICS AND INFORMATICS, VOL III, PROCEEDINGS: COMMUNICATION AND NETWORK SYSTEMS, TECHNOLOGIES AND APPLICATIONS, 2004, :128-133

[50] Hamiltonian cycles in hypercubes with 2n-4 faulty edges [J].

Szepietowski, Andrzej .

INFORMATION SCIENCES, 2012, 215 :75-82

← 1 2 3 4 5 →