کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871669 | 1440188 | 2018 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The fault-diameter and wide-diameter of twisted hypercubes
ترجمه فارسی عنوان
قطر گسل و قطر گسترده ای از هیپو کوب پیچیده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The â-fault-diameter of a graph G is the minimum d such that the diameter of GâX is at most d for any subset X of V(G) of size |X|â¤ââ1. The â-wide-diameter of G is the minimum integer d for which there exist at least â internally vertex disjoint paths of length at most d between any two distinct vertices in G. These two parameters measure the fault tolerance and transmission delay in communication networks modelled by graphs. Twisted hypercubes are variation of hypercubes defined recursively: K1 is the only 0-dimension twisted hypercube, and for nâ¥1, an n-dimensional twisted hypercube Gn is obtained from the disjoint union of two (nâ1)-dimensional twisted hypercubes Gnâ1â² and Gnâ1â²â² by adding a perfect matching between V(Gnâ1â²) and V(Gnâ1â²â²). Recently, two types of twisted hypercubes Zn,k and Hn are introduced in Zhu (2017). This paper gives an upper bound for the n-fault-diameters of special families of twisted hypercubes of dimension n. As a consequence of this result, the n-fault-diameter of Hn is (1+o(1))nlog2n. For k=âlog2nâ2log2log2nâ, the n-fault-diameter of Zn,k is also (1+o(1))nlog2n. This bound is asymptotically optimal, as any n-dimensional twisted hypercube has diameter greater than nlog2n. Then we extend a result in Qi and Zhu (2017) about Zn,k to Hn and prove that the κ(n)-wide-diameter of Hn is (1+o(1))nlog2n.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 235, 30 January 2018, Pages 154-160
Journal: Discrete Applied Mathematics - Volume 235, 30 January 2018, Pages 154-160
نویسندگان
Hao Qi, Xuding Zhu,