The vulnerability of the diameter of enhanced hypercubes

Abstract

For an interconnection network $G$, the {\it $\omega$-wide diameter} $d_{\omega }(G)$ is the least $\ell$ such that any two vertices are joined by $\omega$ internally-disjoint paths of length at most $\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≤ω<n−⌊2k⌋;}\\ d(Q_{n,k})+1& \text{for n−⌊2k⌋≤ω≤n+1.}\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.

9 pages, 1 figure