Wide diameters of de Bruijn graphs

Abstract

The wide diameter of a graph is an important parameter to measure fault-tolerance of interconnection network. This paper proves that for any two vertices in de Bruijn undirected graph UB(d,n), there are 2d-2 internally disjoint paths of length at most 2n+1. Therefore, the (2d-2)-wide diameter of UB(d,n) is not greater than 2n+1.