The wide-diameter of Zn,k

The l-wide-diameter of a graph G is the minimum integer d for which there exist at least l internally disjoint paths of length at most d between any two distinct vertices in G. 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 Z-cubes Zn,k. It is known that Zn,k have diameter at most ⌈nk+1⌉+2k in Zhu (2015). We show that the k-wide-diameter of Zn,k is at most ⌈nk+1⌉+2k+k+4. In particular, if k=⌈log2n−2log2log2n⌉, then the k-wide-diameter of Zn,k is (1+o(1))nlog2n, which is asymptotically optimal.