Restricted fault diameter of hypercube networks (Q1879131)

This paper studies the restricted fault diameter of the \(n\)-dimensional hypercube networks \(Q_n\) \((n\geq 2)\). It is shown that for arbitrary two vertices \(x\) and \(y\) with the distance \(d\) in \(Q_n\) and any set \(F\) with at most \(2n-3\) vertices in \(Q_n-\{x,y\}\), if \(F\) contains neither of the neighbor-sets of \(x\) and \(y\) in \(Q_n\), then the distance \(D(Q_n-F;x,y)\) between \(x\) and \(y\) in \(Q_n-F\), is equal to \(1\) for \(d=1\), not more than \(d+4\) for \(2\leq d\leq n-2, n\geq 4\), not more than \(n+1\) for \(d=n-1, n\geq 3\), equal to \(n\) for \(d=n\). Furthermore, the upper bounds are tight. As an immediate consequence, \(Q_n\) can tolerate up to \(2n-3\) vertex failures and remain diameter \(4\) if \(n=3\) and \(n+2\) if \(n\geq 4\) provided that for each vertex \(x\) in \(Q_n\), all the neighbors of \(x\) do not fail at the same time. This improves \textit{A.-H. Esfahanian}'s result in [IEEE Trans. Comput. 38, 1586--1591 (1989)].