Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871669 | Discrete Applied Mathematics | 2018 | 7 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hao Qi, Xuding Zhu,