Restricted fault diameter of hypercube networks

DOI10.1007/S10255-003-0100-8MaRDI QIDQ1879131zbMATH OpenOpenAlexFDO

Authors Yuping Yao, Jun-Ming Xu, Ke-Li Xu

Publication date 22 September 2004

Published in Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10255-003-0100-8

zbMATH Keywords

hypercubes restricted connectivity restricted fault diameter

Mathematics Subject Classification ID

Distance in graphs (05C12) Connectivity (05C40)

Review text

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)].

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Restricted fault diameter of hypercube networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1879131)