1-vertex-fault-tolerant cycles embedding on folded hypercubes

被引：46

作者：

Hsieh, Sun-Yuan ^{[1
]}

Kuo, Che-Nan ^{[1
]}

Huang, Hui-Ling ^{[2
]}

机构：

[1] Natl Cheng Kung Univ, Dept Comp Sci & Informat Engn, Tainan 701, Taiwan

[2] So Taiwan Univ, Dept Informat Management, Tainan 71005, Taiwan

来源：

DISCRETE APPLIED MATHEMATICS | 2009年 / 157卷 / 14期

关键词：

Folded hypercubes; Interconnection networks; Bipartite graphs; Fault-tolerant embedding; FAULTY VERTICES; BIPANCYCLICITY; NETWORK; GRAPHS; LINKS; EDGES; CUBE;

D O I：

10.1016/j.dam.2009.06.012

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, we focus on a hypercube-like structure, the folded hypercube, which is basically a standard hypercube with some extra links between its nodes. Let f be a faulty vertex in an n-dimensional folded hypercube FQ(n). We show that FQ(n) - {f} contains a fault-free cycle of every even length from 4 to 2(n) - 2 if n >= 3 and, furthermore, every odd length from n + 1 to 2(n) - 1 if n >= 2 and n is even. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：3094 / 3098

页数：5

共 22 条

[11]

2-G

[12]

HSU DF, 1993, NETWORKS, V23

[13]

Leighton F. T., 1992, INTRO PARALLEL ALGOR

[14] Hyper-Hamilton laceable and caterpillar-spannable product graphs [J].