The fault-diameter and wide-diameter of twisted hypercubes

摘要

The l-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 vertical bar X vertical bar = - 1. The -wide-diameter of G is the minimum integer d for which there exist at least l 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: K-1 is the only 0 -dimension twisted hypercube, and for n = 1, an n-dimensional twisted hypercube G(n) is obtained from the disjoint union of two (n - 1)-dimensional twisted hypercubes G'(n-1) and G"(n-1) by adding a perfect matching between V(G'(')(n-)) and V(G"(n-1)). Recently, two types of twisted hypercubes Z(n,k) and lin 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 H-n is (1 + 0(1)) n/log2(n.) For k = [log(2)(n) -2log(2)log(2)(n), the n-fault-diameter of Z(n,k) is also (1 + o(1))n/log2(n). This bound is asymptotically optimal, as any n-dimensional twisted hypercube has diameter greater than n/log2(n) Then we extend a result in Qi and Zhu (2017) about Z(n,)k toll, and prove that the K(n)-wide-diameter of H-n, is (1 + 0(1)) n/log2(n). (C) 2017 Published by Elsevier B.V.