Abstract:
Using the unitary similarity transformation of the adjacency matrix, we obtain
a new upper bound for the independence number of the de Bruijn graph based on the spectrum
of the undirected de Bruijn graph. In the case of a $q$-ary graph of degree $n$
this bound is of the form
\[
\alpha (G_{n}) \le
(1 + \delta _{n})(1-{\pi ^{2}\over 2n^{2}}) {q^{n}\over 2},
\]
where $\delta _{n}\to 0$ as $n\to\infty $.