MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint

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

Frank Bauer and Jürgen Jost


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.

Jun 2, 2010
Jun 3, 2010
MSC Codes:
graph laplacian, largest eigenvalue, Cheeger constant, neighborhood graph

Related publications

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