Wide-diameter of generalized undirected de Bruijn graph UG/sub B/(n, n/sup 2/)

摘要

Caro et al. (1996) have shown that the wide-diameter of the generalized de Bruijn Graphs UG/sub B/ (n, n(n+1)) is 5 for n/spl ges/2. In this paper, we show that the w-diameter of UG/sub B/ (n, n/sup 2/) is 4 where w=2(n-1) and n<4, We also show that UG/sub B/ (n, n/sup 2/) is 2(n-1)-regular and has diameter 2.