### 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 language | English |
---|---|

Pages (from-to) | 370-378 |

Number of pages | 9 |

Journal | Theoretical Computer Science |

Volume | 337 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 2005 Jun 9 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

### Cite this

}

*Theoretical Computer Science*, vol. 337, no. 1-3, pp. 370-378. https://doi.org/10.1016/j.tcs.2005.01.018

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

Research output: Contribution to journal › Article

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 -