The wide-diameter of

详细信息    查看全文

• 作者：Hao Qi ; Xuding Zhu ; ^{xdzhu@zjnu.edu.cn}
• 关键词：Hypercube-like ; Zn ; kZn ; k ; Wide-diameter
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：11 March 2017
• 年：2017
• 卷：219
• 期：Complete
• 页码：193-201
• 全文大小：421 K
• 卷排序：219

文摘

The ll-wide-diameter of a graph GG is the minimum integer dd for which there exist at least ll internally disjoint paths of length at most dd between any two distinct vertices in GG. This parameter measures the fault tolerance and transmission delay in communication networks modelled by graphs. Hypercube-like graphs are widely used as graph models for interconnection networks. In this paper, we study the wide-diameters of a special type of hypercube-like graphs: the ZZ-cubes Zn,kZn,k. It is known that Zn,kZn,k have diameter at most ⌈nk+1⌉+2k in Zhu (2015). We show that the kk-wide-diameter of Zn,kZn,k is at most ⌈nk+1⌉+2k+k+4. In particular, if k=⌈log2n−2log2log2n⌉k=⌈log2n−2log2log2n⌉, then the kk-wide-diameter of Zn,kZn,k is (1+o(1))nlog2n, which is asymptotically optimal.