Springe zum Hauptinhalt
Fakultät für Mathematik
Fakultät für Mathematik
Jochen Harant, Sebastian Richter: A new eigenvalue bound for independent sets

## Jochen Harant, Sebastian Richter: A new eigenvalue bound for independent sets

Author(s):
Jochen Harant
Sebastian Richter
Title:
Jochen Harant, Sebastian Richter: A new eigenvalue bound for independent sets
Electronic source:
application/pdf
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 08, 2014
Mathematics Subject Classification:
05C50 []
05C69 []
Abstract:
Let G be a simple, undirected, and connected graph on n vertices with eigenvalues \lambda_1 <= ... <= \lambda_n. Moreover, let m, \delta, and \alpha denote the size, the minimum degree, and the independence number of G, respectively. W.H. Haemers proved $\alpha <= \frac{-\lambda_1 \lambda_n}{\delta^2 - \lambda_1 \lambda_n}n$ and, if \eta is the largest Laplacian eigenvalue of G, then $\alpha <= \frac{\eta - \delta}{\eta}n$ is shown by C. D. Godsil and M. W. Newman. We prove \alpha <= \frac{2\sigma - 2}{\sigma \delta}m for the largest normalized eigenvalue \sigma of G, if \delta >= 1. Moreover, it is shown that \frac{2\sigma - 2}{\sigma \delta}m < min{\frac{-\lambda_1 \lambda_n}{\delta^2 - \lambda_1 \lambda_n} , \frac{\eta - \delta}{\eta}n} for infinitely many graphs.
Keywords:
independence number, eigenvalues
Language:
English
Publication time:
06/2014