Diskretnaya Matematika, Tome 7 (1995) no. 4, pp. 140-144
Citer cet article
S. Yu. Mel'nikov. Spectra of nonoriented de Bruijn graphs and an upper bound on the independence number for such graphs. Diskretnaya Matematika, Tome 7 (1995) no. 4, pp. 140-144. http://geodesic.mathdoc.fr/item/DM_1995_7_4_a12/
@article{DM_1995_7_4_a12,
author = {S. Yu. Mel'nikov},
title = {Spectra of nonoriented de {Bruijn} graphs and an upper bound on the independence number for such graphs},
journal = {Diskretnaya Matematika},
pages = {140--144},
year = {1995},
volume = {7},
number = {4},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/DM_1995_7_4_a12/}
}
TY - JOUR
AU - S. Yu. Mel'nikov
TI - Spectra of nonoriented de Bruijn graphs and an upper bound on the independence number for such graphs
JO - Diskretnaya Matematika
PY - 1995
SP - 140
EP - 144
VL - 7
IS - 4
UR - http://geodesic.mathdoc.fr/item/DM_1995_7_4_a12/
LA - ru
ID - DM_1995_7_4_a12
ER -
%0 Journal Article
%A S. Yu. Mel'nikov
%T Spectra of nonoriented de Bruijn graphs and an upper bound on the independence number for such graphs
%J Diskretnaya Matematika
%D 1995
%P 140-144
%V 7
%N 4
%U http://geodesic.mathdoc.fr/item/DM_1995_7_4_a12/
%G ru
%F DM_1995_7_4_a12
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 $.
