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

An {\(n\)-dimensional star \(S_n\)} is a graph with vertex set equal to all the permutations of \(n\) numbers. Two vertices of \(S_n\) are adjacent if the corresponding permutations differ by a transposition involving their first elements. In particular, the graph \(S_n\) is \((n-1)\)-regular and bipartite. The author shows that for any set \(W\) of vertices of \(S_n\), \(| W| \leq n-3\) and \(n\geq 4\), and any two vertices \(s\) and \(t\) of \(S_n\), \(s,t\not\in W\), there exists a path between \(s\) and \(t\) of length at least \(n!-2| W| -2\) avoiding vertices contained in the set \(W\). This improves previous results of \textit{J.-H.~Chang, C.-S.~Shin} and \textit{K.-Y.~Chwa} [IEICE Trans. Fund. E82-A~(9), 1953--1964 (1999)], \textit{S.-Y. Hsieh, G.-H.~Chen} and \textit{C.-W.~Ho} [Proc. Int. Conf. Parallel Process., 140--147 (1998)], and \textit{S.-Y.~Hsieh, G.-H.~Chen} and \textit{C.-W.~Ho} [Theor. Comput. Sci. 262, 215--227 (2001; Zbl 0983.68141)] by constant factors.