Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
30/2010

Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplacian

Frank Bauer and Jürgen Jost

Abstract

We study the spectrum of the normalized Laplace operator of a connected graph $\Gamma$. As is well known, the smallest nontrivial eigenvalue measures how difficult it is to decompose $\Gamma$ into two large pieces, whereas the largest eigenvalue controls how close $\Gamma$ is to being bipartite. The smallest eigenvalue can be controlled by the Cheeger constant, and we establish a dual construction that controls the largest eigenvalue. Moreover, we find that the neighborhood graphs $\Gamma[l]$ of order $l\geq2$ encode important spectral information about $\Gamma$ itself which we systematically explore. In particular, we can derive new estimates for the smallest nontrivial eigenvalue that improve the Cheeger estimate for certain graphs, as well as an explicit estimate for the largest eigenvalue from above and below. As applications of such spectral estimates, we provide a criterion for the synchronizability of coupled map lattices, and an estimate for the convergence rate of random walks on graphs.

Received:
Jun 2, 2010
Published:
Jun 3, 2010
MSC Codes:
05C50
Keywords:
graph laplacian, largest eigenvalue, Cheeger constant, neighborhood graph

Related publications

inJournal
2013 Repository Open Access
Frank Bauer and Jürgen Jost

Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator

In: Communications in analysis and geometry, 21 (2013) 4, pp. 787-845