Eigenvalue Conditions for Induced Subgraphs

• Autorzy: Jochen Harant , Julia Niebling , Sebastian Richter
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

induced subgraph; eigenvalue

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 2
• Strony: 355-363

Daty

wydano

2015-05-01

otrzymano

2014-01-21

poprawiono

2014-06-10

zaakceptowano

2014-06-11

online

2015-04-18

Twórcy

autor

Jochen Harant

• Ilmenau University of Technology Department of Mathematics, Germany

autor

Julia Niebling

• Ilmenau University of Technology Department of Mathematics, Germany

autor

Sebastian Richter

• Chemnitz University of Technology Department of Mathematics, Germany

Bibliografia

• [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]
• [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).
• [5] S. Butler, Interlacing for weighted graphs using the normalized Laplacian, Electron. J. Linear Algebra 16 (2007) 90-98.
• [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.
• [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]

Identyfikatory

DOI

10.7151/dmgt.1790