Infoscience

Journal article

On sums of graph eigenvalues

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 graph Laplacian H = -Delta, in increasing order, on a finite graph with vertical bar nu vertical bar vertices and vertical bar epsilon vertical bar edges which is isomorphic to a subgraph of the v-dimensional infinite cubic lattice, then the spectral sums obey a Weyl-type upper bound, a simplification of which reads Sigma(k-1)(j=1) lambda(j) <= pi 2 vertical bar epsilon vertical bar/3(k/vertical bar nu vertical bar)(1+2/v) for each k < vertical bar nu vertical bar This and related estimates for Sigma(k-1)(j=1) lambda(2)(j) provide a family of necessary conditions for the embeddability of the graph in a lattice of dimension nu or less. (C) 2014 Elsevier Inc. All rights reserved.

Fulltext

Related material

Contacts

EPFL authors