Embedding longest fault-free paths onto star graphs with more vertex faults

Research output: Contribution to journalArticle

44 Citations (Scopus)

Abstract

The n-dimensional star graph Sn belongs to a class of bipartite graphs, and it is 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 F(Sn) be the set of vertex faults. Previously, it was shown that when |F(Sn)|≤n-5, Sn with n≥6 can embed a longest fault-free path of length at least n!-2|F(Sn)|-1 (respectively, n!-2|F(Sn)|-2) between two arbitrary vertices in different partite sets (respectively, the same partite set) [Longest fault-free paths in star graphs with vertex faults, Theoretical Computer Science 262 (2001) 215-227]. In this paper, we improve the above result by tolerating more faults (|F(Sn)|≤n-3) to embed a longest fault-free path between two arbitrary vertices in Sn, n≥4.

Original languageEnglish
Pages (from-to)370-378
Number of pages9
JournalTheoretical Computer Science
Volume337
Issue number1-3
DOIs
Publication statusPublished - 2005 Jun 9

Fingerprint

Star Graph
Stars
Fault
Path
Vertex of a graph
Computer science
Arbitrary
Hypercube
Bipartite Graph
n-dimensional
Computer Science
Trivial
Alternatives

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

@article{2ae00287d8554d6eae3efe78ba561fb8,
title = "Embedding longest fault-free paths onto star graphs with more vertex faults",
abstract = "The n-dimensional star graph Sn belongs to a class of bipartite graphs, and it is 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 F(Sn) be the set of vertex faults. Previously, it was shown that when |F(Sn)|≤n-5, Sn with n≥6 can embed a longest fault-free path of length at least n!-2|F(Sn)|-1 (respectively, n!-2|F(Sn)|-2) between two arbitrary vertices in different partite sets (respectively, the same partite set) [Longest fault-free paths in star graphs with vertex faults, Theoretical Computer Science 262 (2001) 215-227]. In this paper, we improve the above result by tolerating more faults (|F(Sn)|≤n-3) to embed a longest fault-free path between two arbitrary vertices in Sn, n≥4.",
author = "Sun-Yuan Hsieh",
year = "2005",
month = "6",
day = "9",
doi = "10.1016/j.tcs.2005.01.018",
language = "English",
volume = "337",
pages = "370--378",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1-3",

}

Embedding longest fault-free paths onto star graphs with more vertex faults. / Hsieh, Sun-Yuan.

In: Theoretical Computer Science, Vol. 337, No. 1-3, 09.06.2005, p. 370-378.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Embedding longest fault-free paths onto star graphs with more vertex faults

AU - Hsieh, Sun-Yuan

PY - 2005/6/9

Y1 - 2005/6/9

N2 - The n-dimensional star graph Sn belongs to a class of bipartite graphs, and it is 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 F(Sn) be the set of vertex faults. Previously, it was shown that when |F(Sn)|≤n-5, Sn with n≥6 can embed a longest fault-free path of length at least n!-2|F(Sn)|-1 (respectively, n!-2|F(Sn)|-2) between two arbitrary vertices in different partite sets (respectively, the same partite set) [Longest fault-free paths in star graphs with vertex faults, Theoretical Computer Science 262 (2001) 215-227]. In this paper, we improve the above result by tolerating more faults (|F(Sn)|≤n-3) to embed a longest fault-free path between two arbitrary vertices in Sn, n≥4.

AB - The n-dimensional star graph Sn belongs to a class of bipartite graphs, and it is 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 F(Sn) be the set of vertex faults. Previously, it was shown that when |F(Sn)|≤n-5, Sn with n≥6 can embed a longest fault-free path of length at least n!-2|F(Sn)|-1 (respectively, n!-2|F(Sn)|-2) between two arbitrary vertices in different partite sets (respectively, the same partite set) [Longest fault-free paths in star graphs with vertex faults, Theoretical Computer Science 262 (2001) 215-227]. In this paper, we improve the above result by tolerating more faults (|F(Sn)|≤n-3) to embed a longest fault-free path between two arbitrary vertices in Sn, n≥4.

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

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

U2 - 10.1016/j.tcs.2005.01.018

DO - 10.1016/j.tcs.2005.01.018

M3 - Article

AN - SCOPUS:18444372047

VL - 337

SP - 370

EP - 378

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1-3

ER -