Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657868 | Theoretical Computer Science | 2005 | 9 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sun-Yuan Hsieh,