JUCS - Journal of Universal Computer Science 13(11): 1501-1513, doi: 10.3217/jucs-013-11-1501
Spectral Densest Subgraph and Independence Number of a Graph
expand article infoReid Andersen‡, Sebastian M. Cioabă§
‡ Microsoft Research, Redmond, United States of America§ University of California, San Diego, United States of America

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

© Reid Andersen, Sebastian Cioabă.
This article is freely available under the J.UCS Open Content License.
Citation: Andersen R, Cioabă SM (2007) Spectral Densest Subgraph and Independence Number of a Graph. JUCS - Journal of Universal Computer Science 13(11): 1501-1513. https://doi.org/10.3217/jucs-013-11-1501
Open Access
Abstract
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.
Keywords
graphs, eigenvalues, densest subgraph, independence number