109 urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891 JUCS - Journal of Universal Computer Science jucs 0948-695X 0948-6968 Journal of Universal Computer Science 10.3217/jucs-013-11-1501 28874 Research Article F.4.1 - Mathematical Logic Spectral Densest Subgraph and Independence Number of a Graph Andersen Reid reidan@microsoft.com 1 Cioabă Sebastian M. 2 Microsoft Research, Redmond, United States of America Microsoft Research Redmond United States of America University of California, San Diego, United States of America University of California San Diego United States of America

Corresponding author: Reid Andersen (reidan@microsoft.com).

Academic editor:

2007 28 11 2007 13 11 1501 1513 772C3B90-37A0-5663-9631-37CA503F1229 6999968 Reid Andersen, Sebastian M. Cioabă This article is freely available under the J.UCS Open Content License.

In this paper, we study spectral versions of the densest subgraph problem and the largest independence subset problem. In the first part, we give an algorithm for identifying small subgraphs with large spectral radius. We also prove a Hoffman-type ratio bound for the order of an induced subgraph whose spectral radius is bounded from above.