×

A new eigenvalue bound for independent sets. (English) Zbl 1315.05086

Summary: Let \(G\) be a simple, undirected, and connected graph on \(n\) vertices with eigenvalues \(\lambda_1 \leq \cdots \leq \lambda_n\). Moreover, let \(m\), \(\delta\), and \(\alpha\) denote the size, the minimum degree, and the independence number of \(G\), respectively. W. H. Haemers [Eigenvalue Techniques in Design and Graph Theory. Mathematical Centre Tracts 121. Amsterdam: Mathematisch Centrum. V (1980; Zbl 0429.05013)] proved \(\alpha \leq \frac{- \lambda_1 \lambda_n}{\delta^2 - \lambda_1 \lambda_n} n\) and, if \(\eta\) is the largest Laplacian eigenvalue of \(G\), then \(\alpha \leq \frac{\eta - \delta}{\eta} n\) is shown by C. D. Godsil and M. W. Newman [J. Comb. Theory, Ser. B 98, No. 4, 721–734 (2008; Zbl 1156.05041)]. We prove \(\alpha \leq \frac{2 \sigma - 2}{\sigma \delta} m\) for the largest normalized eigenvalue \(\sigma\) of \(G\), if \(\delta \geq 1\). For \(\varepsilon > 0\), an infinite family \(\mathcal{F}_\varepsilon\) of graphs is constructed such that \(\frac{2 \sigma - 2}{\sigma \delta} m = \alpha <(\frac{2}{3} + \varepsilon) \min \{\frac{- \lambda_1 \lambda_n}{\delta^2 - \lambda_1 \lambda_n} n, \frac{\eta - \delta}{\eta} n \}\) for all \(G \in \mathcal{F}_\varepsilon\). Moreover, a sequence of graphs is presented showing that the difference between \(\frac{2 \sigma - 2}{\sigma \delta} m\) and D. M. Cvetkovic’s [Publ. Fac. Electrotech. Univ. Belgrade, Ser. Math. Phys. 354–356, 1–50 (1971; Zbl 0238.05102)] upper bound \(\min \{| \{i \in \{1, \ldots, n \} | \lambda_i \leq 0 \} |, | \{i \in \{1, \ldots, n \} | \lambda_i \geq 0 \} | \}\) on \(\alpha\) can be arbitrarily large.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anderson, W. N.; Morley, T. D., Eigenvalues of the Laplacian of a graph, Linear Multilinear Algebra, 18, 141-145 (1985) · Zbl 0594.05046
[2] Bollobás, B.; Nikiforov, V., Graphs and hermitian matrices: eigenvalue interlacing, Discrete Math., 289, 119-127 (2004) · Zbl 1063.05088
[3] Brouwer, A. E.; Haemers, W. H., Spectra of Graphs (2011), Springer · Zbl 0794.05076
[4] Butler, S., Interlacing for weighted graphs using the normalized Laplacian, Electron. J. Linear Algebra, 16, 90-98 (2007) · Zbl 1142.05334
[5] Chung, F. R.K., Laplacian of graphs and Cheeger’s inequalities, (Combinatorics, Paul Erdös is Eighty, Vol. 2 (1996), János Bolyai Math. Soc.: János Bolyai Math. Soc. Budapest), 157-172 · Zbl 0864.05070
[6] Cvetković, D. M., Graphs and their spectra, Univ. Beograd Publ. Elektrotechn. Fak. Ser. Mat. Fiz., 354-356, 1-50 (1971) · Zbl 0238.05102
[7] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs: Theory and Applications (1995), Johann Abrosius Barth Verlag: Johann Abrosius Barth Verlag Heidelberg-Leipzig, third revised and enlarged edition · Zbl 0824.05046
[8] Godsil, C. D.; Newman, M. W., Eigenvalue bounds for independent sets, J. Combin. Theory Ser. B, 98, 721-734 (2008) · Zbl 1156.05041
[9] Haemers, W. H., Interlacing Eigenvalues and graphs, Linear Algebra Appl., 227-228, 593-616 (1995) · Zbl 0831.05044
[10] Haemers, W. H., Eigenvalue Techniques in Design and Graph Theory (1980), Reidel: Reidel Dordrecht, Thesis (T.H. Eindhoven, 1979) = Math. Centr. Tract 121 (Amsterdam, 1980) (pp. 28, 39, 41, 125) · Zbl 0429.05013
[12] Larson, C. E., The independence number project: \( \alpha \)-bounds · Zbl 1230.05226
[13] Lozin, V.; de Werra, D., Foreword: Special issue on stability in graphs and related topics, Discrete Appl. Math., 132, 1-2 (2003) · Zbl 1028.01503
[14] Shigehalli, V. S.; Shettar, V. M., Spectral techniques using normalized adjacency matrices for graph matching, Int. J. Comput. Sci. Math., 2, 4, 371-378 (2011)
[15] van Lint, J. H.; Wilson, R. M., A Course in Combinatorics, 435 (2001), Cambridge University Press · Zbl 0980.05001
[16] Wilf, H. S., Spectral bounds for the clique and independence numbers of graphs, J. Combin. Theory B, 40, 113-117 (1986) · Zbl 0598.05047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.