Fault tolerant routing in the star and pancake interconnection networks (Q2365821)

Given a graph \(G=(V,E)\), a routing \(\rho\) on \(G\) and a set \(F\subset V\cup E\) of ``faulty elements'', the surviving route graph \(R(G,\rho)/F\) of \(G\) is the graph whose vertices are the non-faulty vertices of \(G\) and where \(u\) is adjacent to \(v\) iff the path \(\rho(u,v)\) does not contain elements of \(F\). For practical purposes it is interesting to bound the diameter of \(R(G,\rho)/F\). \textit{D. Dolev}, \textit{J. Halpern}, \textit{B. Simons} and \textit{R. Strong} [Inf. Comput. 72, 180-196 (1987; Zbl 0638.68010)] initiated the study of the diameter \(D(R(G,\rho)/F)\). One of their most interesting results was that for any minimal length routing \(\rho\) on the \(n\)-cube \(H_ n\) the diameter \(D(R(H_ n,\rho)/F)\) is at most 3, as long as \(| F|<n\). \textit{J. Opatrny}, \textit{N. Sprinivasan} and \textit{V. Alagar} [IEEE Trans. Circuits Syst. 36, 23-30 (1989; Zbl 0666.94026)] present a class of graphs \({\mathcal G}\) such that for any \(G\in{\mathcal G}\) and for any minimal length routing \(\rho\) on \(G\) the diameter \(D(R(G,\rho)/F)\) is at most 2, as long as \(F\) consists of nodes only and \(| F|\) is less than the connectivity of \(G\). In spite of the considerable progress made on the problem of bounding \(D(R(G,\rho)/F)\) no other graphs are known to exhibit such a good performance. The paper shows that a recently proposed interconnection network enjoys similar properties. The \(n\)-star graph \(S_ n\) and the \(n\)-pancake graph \(P_ n\) were proposed by \textit{S. B. Akers} and \textit{B. Krishnamurthy} [IEEE Trans. Comput. 36, 885-888 (1987; Zbl 0641.94049)] and have recently received much attention because of their rich structure, small diameter and symmetry property. The paper shows that for any minimal length routing \(\rho D(R(S_ n,\rho)/F)\leq 3\), as long as \(| F|<n\). Moreover, it is proven that \(D(R(P_ n,\rho)/F)\leq 4\), as long as \(| F|<n\) and \(\rho\) belongs to a particular class of routings, which is conjectured to contain all minimal length routings.