تقرير
The vulnerability of the diameter of enhanced hypercubes
| العنوان: | The vulnerability of the diameter of enhanced hypercubes |
|---|---|
| المؤلفون: | Ma, Meijie, West, Douglas B., Xu, Jun-Ming |
| سنة النشر: | 2016 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Discrete Mathematics, Mathematics - Combinatorics |
| الوصف: | 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\ge3$ and $2\le k\le n$ we prove $$ D_\omega(Q_{n,k})=d_\omega(Q_{n,k})=\begin{cases} d(Q_{n,k}) & \textrm{for $1 \leq \omega < n-\lfloor\frac{k}{2}\rfloor$;}\\ d(Q_{n,k})+1 & \textrm{for $n-\lfloor\frac{k}{2}\rfloor \leq \omega \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. Comment: 9 pages, 1 figure |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1604.02906 |
| رقم الأكسشن: | edsarx.1604.02906 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |