# Asymptotically-Tight Bounds on the Number of Cycles in Generalized de {B}ruijn-Good Graphs

## Ueli Maurer

```
```The number of cycles of length $k$ that can be generated by $q$-ary
$n$-stage feedback shift-registers is studied. This problem is
equivalent to finding the number of cycles of length $k$ in the natural
generalization, from binary to \qa digits, of the so-called
de Bruijn-Good graphs \cite{brychri,debrui}. The number of cycles of
length $k$ in the \qa graph $\gqn$ of order $n$ is denoted by $\bqnk$.
Known results about $\beta^{(2)}(n,k)$ are summarized and extensive new
numerical data is presented. Lower and upper bounds on $\bqnk$ are
derived showing that, for large $k$, virtually all \qa cycles of length
$k$ are contained in $\gqn$ for $n>\tlqk$, but virtually none of these
cycles is contained in $\gqn$ for $n<\tlqkm$. More precisely, if
$\nyqk$ denotes the total number of \qa length $k$ cycles, then for any
function $f(k)$ that grows without bounds as $k\rightarrow\infty$ (e.g.
$f(k)=\log_{q}\!\log_{q}\!\log_{q}k$), the bounds obtained on $\bqnk$
are asymptotically tight in the sense that they imply
\begin{eqnarray}
\lki\frac{\beta^{(q)}(n(k),k)}{\nyqk}&=&0 \makebox{ for }
n(k)=\lfloor\tlqkm-f(k)\rfloor, \makebox{ and} \nonumber\\
\lki\frac{\beta^{(q)}(n(k),k)}{\nyqk}&=&1 \makebox{ for }
n(k)=\lfloor\tlqk+f(k)\rfloor,\nonumber
\end{eqnarray}
where $\lfloor.\rfloor$ denotes the integer part of the enclosed number.
Finally, some approximations for $\bqnk$ are given that make the global
behavior of $\bqnk$ more transparent.