The diameter of the generalized de Bruijn graph UGB (n,m) where n < m <_ n3 and n divides m - Zeratsion, Tedros Weldemicael (2000)
The generalized de Bruijn digraph denoted by Gb (n,m) is defined to be the digraph with m vertices labelled by 0,1,2,..., m-1 and with the adjacency defined as follows : If i is a vertex in Gb (n,m) then i is connected to each vertex in the set E(i), where E(i) = {ni +a (mod m) and a e [0, n-1]}, that is, (i,j) e E (Gb(n,m)) if and only if i,j e V (Gb(n,m)) and j - ni + a(mod m), for some a e [0,n-1], where [a,b] denotes the set of integers between a and b inclusive. The generalized de Bruijn graph denoted by UGb (n,m) is defined to be the undirected version of Gb (n,m) obtained by replacing each arc by an undirected edge and eliminating self-loops and multi-edges. Du and Hwang [7] showed that the diameter of Gb (n,m) does not exceed [log nm], and that Gb (n,m) is hamiltonian when gcd(n,m) > 1, but it is not when gcd(n,m) = 1 and n > 2 as proved by Du, Hwang, and Zhang [5]. Naturally, the question of diameter, hamiltonicity and wide-diameter is asked for the undirected version. Escuadro has shown that UGb(n,m) is 1(n-1)- regular with diameter 2, when m=n2, while Nochefranca and Sy [19] have shown that UGb(n,m) is 2(n-1)- regular with diameter 3, when m = n (n+1). In this paper, we will show that the diameter of UGb(n,m) is 2 for any m in [n+1,n2] where n divides m and that the diameter is 3 for any m in [n2 + 1, n3] where n divides m.