On the diameter of the generalized undirected de Bruijn graphs UG B ( n , m ), n 2 < m ≤ n 3

The generalized de Bruijn digraph G B ( n , m ) is the digraph ( V , A ) where V = {0, 1,…, m − 1} and ( i , j ) ∈ A if and only if j ≡ i n + α (mod m ) for some α ∈ {0, 1, 2,…, n − 1}. By replacing each arc of G B ( n , m ) with an undirected edge and eliminating loops and multi‐edges, we obtain the generalized undirected de Bruijn graph U G B ( n , m ). In this article, we prove that when 2 n 2 ≤ m ≤ n 3 the diameter of U G B ( n , m ) is equal to 3. We also show that for pairs ( n , m ) where n 2 < m < 2 n 2 the diameter of U G B ( n , m ) can be 2 or 3. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008