Elsevier, Linear Algebra and its Applications, 5(433), p. 1031-1037, 2010
DOI: 10.1016/j.laa.2010.04.029
Full text: Download
Let G be a simple graph with least eigenvalue lambda and let S be a set of vertices in G which induce a subgraph with mean degree k. We use a quadratic programming technique in conjunction with the main angles of G to establish an upper bound of the form vertical bar S vertical bar <= inf{(k + t)q(G)(t) : t > - lambda} where q(G) is a rational function determined by the spectra of G and its complement. In the case k = 0 we obtain improved bounds for the independence number of various benchmark graphs.