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

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.