Search

In this paper, we will show that the diameter of the generalized De Bruijn graph UGB (n, n(n+1)) is 3 using an automorphism of the graph, and we will also give an algorithm to find a hamiltonian cycle of UGB (n, n(n+1)) for all integers n≥2.

The generalized de Bruijn graph UG/sub B/(n, n/sup 2/+1) is the graph with vertex set V={0, 1, ..., n/sup 2/} and the neighborhood N(i) of i/spl isin/V is N(i)=X(i)/spl cap/Y(i) where X(i)={in+d(modn/sup 2/+1):/spl alpha//spl isin/D and [(2i-/spl alpha/n)+(n/sup 2/+1)Z]/spl cap/D=O}, Y(i)={(/spl beta/-i)n(modn/sup 2/+1):/spl beta//spl isin/D and [(/spl beta/-2i)n+(n/sup 2/+1)Z]/spl cap/D=O}. In this paper, we show that the diameter of UG/sub B/(n, n/sup 2/+1) is at most 4 for n odd and n/spl ges/5.