Article ID Journal Published Year Pages File Type
6871669 Discrete Applied Mathematics 2018 7 Pages PDF
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
, ,