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