On the independence number of de Bruijn graphs

Pietro Majer, Matteo Novaga

We derive the asymptotic formula $\hat{I}\pm (k,q)=\hat{I}{»}_{k-1}{q}^k+o(q^k)$, where $\hat{I}\pm (k,q)$ is the independence number of the de Bruijn graph $B(k,q)$, and $\hat{I}{»}_{k-1}$ is a constant arising from…