On sums of graph eigenvalues

DOI10.1016/J.LAA.2014.05.001zbMATH Open1305.05127arXiv1308.5340OpenAlexW2592570621MaRDI QIDQ2015086FDOQ2015086

Authors: Joachim Stubbe, Evans M. II Harrell 

Publication date: 18 June 2014

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: We use two variational techniques to prove upper bounds for sums of the lowest several eigenvalues of matrices associated with finite, simple, combinatorial graphs. These include estimates for the adjacency matrix of a graph and for both the standard combinatorial Laplacian and the renormalized Laplacian. We also provide upper bounds for sums of squares of eigenvalues of these three matrices. Among our results, we generalize an inequality of Fiedler for the extreme eigenvalues of the graph Laplacian to a bound on the sums of the smallest (or largest) k such eigenvalues, k < n. Furthermore, if lambda_j are the eigenvalues of the positive graph Laplacian H, in increasing order, on a finite graph with |V| vertices and |E| edges which is isomorphic to a subgraph of the

u-dimensional infinite cubic lattice, then the spectral sums obey a Weyl-type upper bound, a simplification of which reads ${\displaystyle }$ sum_{j=1}^{k-1}{lambda_j} le frac{pi^2 |mathcal{E}|}{3} left(frac{k}{|mathcal{V}|} ight)^{1+frac{2}{ u}} ${\displaystyle }$ for each k < |V|. This and related estimates for sums of lambda_j^2 provide a family of necessary conditions for the embeddability of the graph in a lattice of dimension

u or less.

Full work available at URL: https://arxiv.org/abs/1308.5340

Recommendations

• An interlacing approach for bounding the sum of Laplacian eigenvalues of graphs
• An interlacing approach for bounding the sum of Laplacian eigenvalues of graphs
• Eigenvalue sum estimates for lattice subgraphs
• Eigenvalues of the Laplacian of a graph^∗
• Eigenvalue sums of combinatorial magnetic Laplacians on finite graphs

zbMATH Keywords

graph spectrumWeyl lawsums of eigenvalues

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Variational methods for eigenvalues of operators (49R05) Eigenvalue problems for linear operators (47A75)

Cites Work

• Graph theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Eigenspaces of graphs
• An introduction to the theory of graph spectra
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Schrödinger equation and the eigenvalue problem
• Title not available (Why is that?)
• On the Eigenvalues of Vibrating Membranes^†
• Upper bounds for the Neumann eigenvalues on a bounded domain in Euclidean space
• On sum of powers of the Laplacian eigenvalues of graphs
• On trace identities and universal eigenvalue estimates for some partial differential operators
• Laplacian eigenvectors of graphs. Perron-Frobenius and Faber-Krahn type theorems
• Trace identities for commutators, with applications to the distribution of eigenvalues

Cited In (10)

• Eigenvalue sums of combinatorial magnetic Laplacians on finite graphs
• Two-term, asymptotically sharp estimates for eigenvalue means of the Laplacian
• On the sum of Laplacian eigenvalues of graphs
• Geometric bounds for the magnetic Neumann eigenvalues in the plane
• Graph Embeddings and Laplacian Eigenvalues
• On the spectral asymptotics for the buckling problem
• Semiclassical bounds for spectra of biharmonic operators
• Metric uniformization and spectral bounds for graphs
• Semiclassical estimates for eigenvalue means of Laplacians on spheres
• Eigenvalue sum estimates for lattice subgraphs

This page was built for publication: On sums of graph eigenvalues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2015086)