The vulnerability of the diameter of enhanced hypercubes

For an interconnection network $G$, the {\it $\omega$-wide diameter} $d_{\omega }(G)$ is the least $\mathrm{\ell }$ such that any two vertices are joined by $\omega$ internally-disjoint paths of length at most $\mathrm{\ell }$, and the {\it $(\omega -1)$-fault diameter} $D_{\omega }(G)$ is the maximum diameter of a subgraph obtained by deleting fewer than $\omega$ 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\ge 3$ and $2\le k\le n$ we prove $$D_{\omega }(Q_{n,k})=d_{\omega }(Q_{n,k})=\{\begin{array}{ll}d(Q_{n,k})& \text{for }1\le \omega <n-\lfloor \frac{k}{2}\rfloor \text{;}\\ d(Q_{n,k})+1& \text{for }n-\lfloor \frac{k}{2}\rfloor \le \omega \le n+1\text{.}\end{array}$$ 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.