The vulnerability of the diameter of enhanced hypercubes

For an interconnection network $G$, the {\it $ω$-wide diameter} $d_ω(G)$ is the least $\ell$ such that any two vertices are joined by $ω$ internally-disjoint paths of length at most $\ell$, and the {\it $(ω-1)$-fault diameter} $D_ω(G)$ is the maximum diameter of a subgraph obtained by deleting fewer than $ω$ vertices of $G$. The enhanced hypercube $Q_{n,k}$ is a variant of the well-known hypercube. Yang, Chang, Pai, and Chan gave an upper bound for $d_{n+1}(Q_{n,k})$ and $D_{n+1}(Q_{n,k})$ and posed the problem of finding the wide diameters and fault diameters of $Q_{n,k}$. By constructing internally disjoint paths between any two vertices in the enhanced hypercube, for $n\ge3$ and $2\le k\le n$ we prove $D_ω(Q_{n,k})=d_ω(Q_{n,k})=\begin{cases} d(Q_{n,k}) & \textrm{for $1 \leq ω< n-\lfloor\frac{k}{2}\rfloor$;}\\ d(Q_{n,k})+1 & \textrm{for $n-\lfloor\frac{k}{2}\rfloor \leq ω\leq n+1$.} \end{cases}$ where $d(Q_{n,k})$ is the diameter of $Q_{n,k}$. These results mean that interconnection networks modelled by enhanced hypercubes are extremely robust.

No reviews yet.

No comments yet.