A further result on fault-free cycles in faulty folded hypercubes

Sun Yuan Hsieh; Che Nan Kuo; Hsin Hung Chou

doi:10.1016/j.ipl.2009.10.003

A further result on fault-free cycles in faulty folded hypercubes

Sun Yuan Hsieh, Che Nan Kuo, Hsin Hung Chou

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Article › peer-review

23 Citations (Scopus)

Abstract

Folded hypercube is a well-known variation of the hypercube structure and can be constructed from a hypercube by adding a link to every pair of nodes with complementary addresses. Let F F_v (respectively, F F_e) be the set of faulty nodes (respectively, faulty links) in an n-dimensional folded hypercube F Q_n. Fu has showed that F Q_n - F F_v - F F_e for n ≥ 3 contains a fault-free cycle of length at least 2ⁿ - 2 | F F_v | if | F F_v | + | F F_e | ≤ 2 n - 4 and | F F_e | ≤ n - 1. In this paper, we further consider the constraints | F F_v | + | F F_e | ≤ 2 n - 4 and | F F_e | ≥ n that were not covered by Fu's result. We obtain the same lower bound of the longest fault-free cycle length, 2ⁿ - 2 | F F_v |, under the constraints that (1) | F F_v | + | F F_e | ≤ 2 n - 4 and (2) every node in F Q_n is incident to at least two fault-free links.

Original language	English
Pages (from-to)	41-43
Number of pages	3
Journal	Information Processing Letters
Volume	110
Issue number	2
DOIs	https://doi.org/10.1016/j.ipl.2009.10.003
Publication status	Published - 2009 Dec 16

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/j.ipl.2009.10.003

Cite this

@article{409c234cfeb84c6ca10e6c3df6921d0c,

title = "A further result on fault-free cycles in faulty folded hypercubes",

abstract = "Folded hypercube is a well-known variation of the hypercube structure and can be constructed from a hypercube by adding a link to every pair of nodes with complementary addresses. Let F Fv (respectively, F Fe) be the set of faulty nodes (respectively, faulty links) in an n-dimensional folded hypercube F Qn. Fu has showed that F Qn - F Fv - F Fe for n ≥ 3 contains a fault-free cycle of length at least 2n - 2 | F Fv | if | F Fv | + | F Fe | ≤ 2 n - 4 and | F Fe | ≤ n - 1. In this paper, we further consider the constraints | F Fv | + | F Fe | ≤ 2 n - 4 and | F Fe | ≥ n that were not covered by Fu's result. We obtain the same lower bound of the longest fault-free cycle length, 2n - 2 | F Fv |, under the constraints that (1) | F Fv | + | F Fe | ≤ 2 n - 4 and (2) every node in F Qn is incident to at least two fault-free links.",

author = "Hsieh, {Sun Yuan} and Kuo, {Che Nan} and Chou, {Hsin Hung}",

year = "2009",

month = dec,

day = "16",

doi = "10.1016/j.ipl.2009.10.003",

language = "English",

volume = "110",

pages = "41--43",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - A further result on fault-free cycles in faulty folded hypercubes

AU - Hsieh, Sun Yuan

AU - Kuo, Che Nan

AU - Chou, Hsin Hung

PY - 2009/12/16

Y1 - 2009/12/16

N2 - Folded hypercube is a well-known variation of the hypercube structure and can be constructed from a hypercube by adding a link to every pair of nodes with complementary addresses. Let F Fv (respectively, F Fe) be the set of faulty nodes (respectively, faulty links) in an n-dimensional folded hypercube F Qn. Fu has showed that F Qn - F Fv - F Fe for n ≥ 3 contains a fault-free cycle of length at least 2n - 2 | F Fv | if | F Fv | + | F Fe | ≤ 2 n - 4 and | F Fe | ≤ n - 1. In this paper, we further consider the constraints | F Fv | + | F Fe | ≤ 2 n - 4 and | F Fe | ≥ n that were not covered by Fu's result. We obtain the same lower bound of the longest fault-free cycle length, 2n - 2 | F Fv |, under the constraints that (1) | F Fv | + | F Fe | ≤ 2 n - 4 and (2) every node in F Qn is incident to at least two fault-free links.

AB - Folded hypercube is a well-known variation of the hypercube structure and can be constructed from a hypercube by adding a link to every pair of nodes with complementary addresses. Let F Fv (respectively, F Fe) be the set of faulty nodes (respectively, faulty links) in an n-dimensional folded hypercube F Qn. Fu has showed that F Qn - F Fv - F Fe for n ≥ 3 contains a fault-free cycle of length at least 2n - 2 | F Fv | if | F Fv | + | F Fe | ≤ 2 n - 4 and | F Fe | ≤ n - 1. In this paper, we further consider the constraints | F Fv | + | F Fe | ≤ 2 n - 4 and | F Fe | ≥ n that were not covered by Fu's result. We obtain the same lower bound of the longest fault-free cycle length, 2n - 2 | F Fv |, under the constraints that (1) | F Fv | + | F Fe | ≤ 2 n - 4 and (2) every node in F Qn is incident to at least two fault-free links.

UR - http://www.scopus.com/inward/record.url?scp=70449672341&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70449672341&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2009.10.003

DO - 10.1016/j.ipl.2009.10.003

M3 - Article

AN - SCOPUS:70449672341

SN - 0020-0190

VL - 110

SP - 41

EP - 43

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

A further result on fault-free cycles in faulty folded hypercubes

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this