On the Diameter of the Generalized Undirected De Bruijn Graphs

Abstract

The generalized de Bruijn digraph denoted by $G_B(n,m)$ is the digraph $(V,A)$ where $V=\{0,1,\dots ,m-1\}$ and $(i,j)\in A$ if and only if $j\equiv ni+\alpha (\mathrm{mod}m)$ for some $\alpha \in \{0,1,\dots ,n-1\}$. By replacing each arc of $G_B(n,m)$ with an undirected edge and eliminating loops and multi-edges, we obtain a generalized undirected de Bruijn graph $U{G}_B(n,m)$. In this paper, we prove that the diameter of $U{G}_B(n,m)$ is equal to 3 whenever $n\ge 2$ and $n^2+(\frac{\sqrt{5}+1}{2})\le m\le 2n^2.$