On the diameter of the generalized undirected de Bruijn graphsUGB(n,m),n2
Jyhmin Kuo, Hung‐Lin Fu · Networks · 2008
Abstract The generalized de Bruijn digraphGB(n,m) is the digraph (V,A) whereV= {0, 1,…,m− 1} and (i,j) ∈Aif and only ifj≡in+α(modm) for someα∈ {0, 1, 2,…,n− 1}. By replacing each arc ofGB(n,m) with an undirected edge and eliminating loops and multi‐edges, we obtain the generalized undirected de Bruijn graphUGB(n,m). In this article, we prove that when 2n2≤m≤n3the diameter ofUGB(n,m) is equal to 3. We also show that for pairs (n,m) wheren2<m< 2n2the diameter ofUGB(n,m) can be 2 or 3. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008