Necessary conditions for an undirected graph G to contain a graph H as induced subgraph involving the smallest ordinary or the largest normalized Laplacian eigenvalue of G are presented.
@article{bwmeta1.element.doi-10_7151_dmgt_1790,
author = {Jochen Harant and Julia Niebling and Sebastian Richter},
title = {Eigenvalue Conditions for Induced Subgraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {355-363},
zbl = {1311.05113},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1790}
}
Jochen Harant; Julia Niebling; Sebastian Richter. Eigenvalue Conditions for Induced Subgraphs. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 355-363. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1790/
[1] W.N. Anderson Jr. and T.D. Morley, Eigenvalues of the Laplacian of a graph, Linear Multilinear Algebra 18 (1985) 141-145. doi:10.1080/03081088508817681[Crossref] | Zbl 0594.05046
[2] D.P. Bertsekas, Nonlinear Programming: Second Edition (Athena Scientific, Belmont, Massachusetts 1999) page 278, Proposition 3.1.1.
[3] B. Bollobas and V. Nikiforov, Graphs and Hermitian matrices: eigenvalue interlac- ing, Discrete Math. 289 (2004) 119-127. doi:10.1016/j.disc.2004.07.011[Crossref]
[4] A.E. Brouwer and W.H. Haemers, Spectra of Graphs (Springer Verlag, 2011). | Zbl 1231.05001
[5] S. Butler, Interlacing for weighted graphs using the normalized Laplacian, Electron. J. Linear Algebra 16 (2007) 90-98. | Zbl 1142.05334
[6] F.R.K. Chung, Laplacian of graphs and Cheeger’s inequalities, in: Combinatorics, Paul Erdős is Eighty, Janos Bolyai Math. Soc., Budapest Vol. 2, 1996, 157-172.
[7] D.M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and Applications (Johann Abrosius Barth Verlag, Heidelberg-Leipzig, 1995).
[8] R. Diestel, Graph Theory (Springer, Graduate Texts in Mathematics, 173, 2000).
[9] W.H. Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl. 1995 (227-228) 593-616. doi:10.1016/0024-3795(95)00199-2[Crossref]
[10] F.J. Hall, The Adjacency Matrix, Standard Laplacian, and Normalized Laplacian, and Some Eigenvalue Interlacing Results, Department of Mathematics and Statistics Georgia State University Atlanta, GA 30303. http://www2.cs.cas.cz/semincm/lectures/2010-04-13-Hall.pdf
[11] J. Harant and S. Richter, A new eigenvalue bound for independent sets, Discrete Math. accepted. http://www.tu-chemnitz.de/mathematik/preprint/2014/PREPRINT_08.pdf. | Zbl 1315.05086
[12] V.S. Shigehalli and V.M. Shettar, Spectral techniques using normalized adjacency matrices for graph matching, Int. J. Comput. Sci. Math. 2 (2011) 371-378.
[13] Xiao-Dong Zhang, The Laplacian eigenvalues of graphs: a survey. arXiv:1111.2897v1 [math.CO] 12Nov2011
[14] R. Zurmuhl, Matrizen (Springer 1950) 152-158. doi:10.1007/978-3-642-53289-4_16 [Crossref]