Eigenvalue Conditions for Induced Subgraphs

Jochen Harant; Julia Niebling; Sebastian Richter

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 2, page 355-363
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Jochen Harant, Julia Niebling, and Sebastian Richter. "Eigenvalue Conditions for Induced Subgraphs." Discussiones Mathematicae Graph Theory 35.2 (2015): 355-363. <http://eudml.org/doc/271093>.

@article{JochenHarant2015,
abstract = {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.},
author = {Jochen Harant, Julia Niebling, Sebastian Richter},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {induced subgraph; eigenvalue},
language = {eng},
number = {2},
pages = {355-363},
title = {Eigenvalue Conditions for Induced Subgraphs},
url = {http://eudml.org/doc/271093},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Jochen Harant
AU - Julia Niebling
AU - Sebastian Richter
TI - Eigenvalue Conditions for Induced Subgraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 2
SP - 355
EP - 363
AB - 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.
LA - eng
KW - induced subgraph; eigenvalue
UR - http://eudml.org/doc/271093
ER -

References

top
  1. [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] Zbl0594.05046
  2. [2] D.P. Bertsekas, Nonlinear Programming: Second Edition (Athena Scientific, Belmont, Massachusetts 1999) page 278, Proposition 3.1.1. 
  3. [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. [4] A.E. Brouwer and W.H. Haemers, Spectra of Graphs (Springer Verlag, 2011). Zbl1231.05001
  5. [5] S. Butler, Interlacing for weighted graphs using the normalized Laplacian, Electron. J. Linear Algebra 16 (2007) 90-98. Zbl1142.05334
  6. [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. [7] D.M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and Applications (Johann Abrosius Barth Verlag, Heidelberg-Leipzig, 1995). 
  8. [8] R. Diestel, Graph Theory (Springer, Graduate Texts in Mathematics, 173, 2000). 
  9. [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. [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. [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. Zbl1315.05086
  12. [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. [13] Xiao-Dong Zhang, The Laplacian eigenvalues of graphs: a survey. arXiv:1111.2897v1 [math.CO] 12Nov2011 
  14. [14] R. Zurmuhl, Matrizen (Springer 1950) 152-158. doi:10.1007/978-3-642-53289-4_16 [Crossref] 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.