Longest fault-free paths in star graphs with vertex faults

Sun Yuan Hsieh; Gen Huey Chen; Chin Wen Ho

doi:10.1016/S0304-3975(00)00190-0

Longest fault-free paths in star graphs with vertex faults

Sun Yuan Hsieh, Gen Huey Chen, Chin Wen Ho

Department of Computer Science and Information Engineering

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

6 Scopus citations

Abstract

The star graph S_n has been recognized as an attractive alternative to the hypercube. Since S₁, S₂, and S₃ have trivial structures, we focus our attention on S_n with n ≥ 4 in this paper. Let F_v denote the set of faulty vertices in S_n. We show that when |F_v| ≤ n - 5 ,S_n with n ≥ 6 contains a fault-free path of length n! - 2|F_v| - 2 (n! - 2 |F_v| - 1) between arbitrary two vertices of even (odd) distance. Since S_n is bipartite with two partite sets of equal size, the path is longest for the worst-case scenario. The situation of n ≥ 4 and |F_v| ≥ n - 5 is also discussed.

Original language	English
Pages (from-to)	215-227
Number of pages	13
Journal	Theoretical Computer Science
Volume	262
Issue number	1-2
DOIs	https://doi.org/10.1016/S0304-3975(00)00190-0
State	Published - 2001

Keywords

Bipartite graph
Cayley graph
Fault-tolerant embedding
Graph-theoretic interconnection network
Hamiltonian path
Longest path
Star graph

Access to Document

10.1016/S0304-3975(00)00190-0

Cite this

@article{289e48d2a46a48bba799be8a97866573,

title = "Longest fault-free paths in star graphs with vertex faults",

abstract = "The star graph Sn has been recognized as an attractive alternative to the hypercube. Since S1, S2, and S3 have trivial structures, we focus our attention on Sn with n ≥ 4 in this paper. Let Fv denote the set of faulty vertices in Sn. We show that when |Fv| ≤ n - 5 ,Sn with n ≥ 6 contains a fault-free path of length n! - 2|Fv| - 2 (n! - 2 |Fv| - 1) between arbitrary two vertices of even (odd) distance. Since Sn is bipartite with two partite sets of equal size, the path is longest for the worst-case scenario. The situation of n ≥ 4 and |Fv| ≥ n - 5 is also discussed.",

keywords = "Bipartite graph, Cayley graph, Fault-tolerant embedding, Graph-theoretic interconnection network, Hamiltonian path, Longest path, Star graph",

author = "Hsieh, {Sun Yuan} and Chen, {Gen Huey} and Ho, {Chin Wen}",

year = "2001",

doi = "10.1016/S0304-3975(00)00190-0",

language = "???core.languages.en_GB???",

volume = "262",

pages = "215--227",

journal = "Theoretical Computer Science",

issn = "0304-3975",

number = "1-2",

}

TY - JOUR

T1 - Longest fault-free paths in star graphs with vertex faults

AU - Hsieh, Sun Yuan

AU - Chen, Gen Huey

AU - Ho, Chin Wen

PY - 2001

Y1 - 2001

N2 - The star graph Sn has been recognized as an attractive alternative to the hypercube. Since S1, S2, and S3 have trivial structures, we focus our attention on Sn with n ≥ 4 in this paper. Let Fv denote the set of faulty vertices in Sn. We show that when |Fv| ≤ n - 5 ,Sn with n ≥ 6 contains a fault-free path of length n! - 2|Fv| - 2 (n! - 2 |Fv| - 1) between arbitrary two vertices of even (odd) distance. Since Sn is bipartite with two partite sets of equal size, the path is longest for the worst-case scenario. The situation of n ≥ 4 and |Fv| ≥ n - 5 is also discussed.

AB - The star graph Sn has been recognized as an attractive alternative to the hypercube. Since S1, S2, and S3 have trivial structures, we focus our attention on Sn with n ≥ 4 in this paper. Let Fv denote the set of faulty vertices in Sn. We show that when |Fv| ≤ n - 5 ,Sn with n ≥ 6 contains a fault-free path of length n! - 2|Fv| - 2 (n! - 2 |Fv| - 1) between arbitrary two vertices of even (odd) distance. Since Sn is bipartite with two partite sets of equal size, the path is longest for the worst-case scenario. The situation of n ≥ 4 and |Fv| ≥ n - 5 is also discussed.

KW - Bipartite graph

KW - Cayley graph

KW - Fault-tolerant embedding

KW - Graph-theoretic interconnection network

KW - Hamiltonian path

KW - Longest path

KW - Star graph

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

U2 - 10.1016/S0304-3975(00)00190-0

DO - 10.1016/S0304-3975(00)00190-0

M3 - 期刊論文

AN - SCOPUS:0034921974

SN - 0304-3975

VL - 262

SP - 215

EP - 227

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -

Longest fault-free paths in star graphs with vertex faults

Abstract

Keywords

Access to Document

Fingerprint

Cite this