Published in

Elsevier, Linear Algebra and its Applications, 5(433), p. 1031-1037, 2010

DOI: 10.1016/j.laa.2010.04.029

Links

Tools

Export citation

Search in Google Scholar

Spectral upper bounds for the order of a k-regular induced subgraph

Journal article published in 2010 by Domingos M. Cardoso ORCID, Peter Rowlinson
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

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.