Embedding even cycles on folded hypercubes with conditional faulty edges

被引：17

作者：

Cheng, Dongqin ^{[1
,2
]}

Hao, Rong-Xia ^{[2
]}

Feng, Yan-Quan ^{[2
]}

机构：

[1] Jinan Univ, Dept Math, Guangzhou 510632, Guangdong, Peoples R China

[2] Beijing Jiaotong Univ, Dept Math, Beijing 100044, Peoples R China

来源：

INFORMATION PROCESSING LETTERS | 2015年 / 115卷 / 12期

基金：

中国国家自然科学基金;

关键词：

Folded hypercube; Cycle embedding; Conditional fault model; Faulty edge; Interconnection network; BIPANCYCLICITY;

D O I：

10.1016/j.ipl.2015.07.015

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Let FFe be the set of vertical bar FFe vertical bar <= 2n - 4 faulty edges in an n-dimensional folded hypercube FQ(n) such that each vertex in FQ(n) is incident to at least two fault-free edges. Under this assumption, we show that every edge of FQ(n) - FFe lies on a fault-free cycle of every even length from 6 to 2(n), where n >= 5. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：945 / 949

页数：5

共 10 条

[1]

BHUYAN LN, 1984, IEEE T COMPUT, V33, P323, DOI 10.1109/TC.1984.1676437

[2]

Bondy J.A., 2008, GTM

[3] Odd cycles embedding on folded hypercubes with conditional faulty edges [J].

Cheng, Dongqin ;

Hao, Rong-Xia ;

Feng, Yan-Quan .

INFORMATION SCIENCES, 2014, 282 :180-189

[4] PROPERTIES AND PERFORMANCE OF FOLDED HYPERCUBES [J].

ELAMAWY, A ;

LATIFI, S .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1991, 2 (01) :31-42

[5] Embedding paths of variable lengths into hypercubes with conditional link-faults [J].

Kueng, Tz-Liang ;

Lin, Cheng-Kuan ;

Liang, Tyne ;

Tan, Jimmy J. M. ;

Hsu, Lih-Hsing .

PARALLEL COMPUTING, 2009, 35 (8-9) :441-454

[6]

Leighton F.T., 1992, Introduction to Parallel Algorithms and Architectures: Arrays Trees Hypercubes

[7] Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes [J].

Li, TK ;

Tsai, CH ;

Tan, JJM ;

Hsu, LH .

INFORMATION PROCESSING LETTERS, 2003, 87 (02) :107-110

[8] Linear array and ring embeddings in conditional faulty hypercubes [J].

Tsai, CH .

THEORETICAL COMPUTER SCIENCE, 2004, 314 (03) :431-443

[9] Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes [J].

Tsai, Chang-Hsiung ;

Lai, Yung-Chun .

INFORMATION SCIENCES, 2007, 177 (24) :5590-5597

[10]

Xu JM, 2006, AUSTRALAS J COMB, V35, P7

← 1 →