Spectra of nonoriented de Bruijn graphs and an upper bound on the independence number for such graphs

S. Yu. Mel'nikov

Diskretnaya Matematika, Tome 7 (1995) no. 4, pp. 140-144.

Résumé

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 $.