تقرير
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 |
الوصف غير متاح. |