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

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

2009-10-16

arxiv.org/abs/0910.3118v4

Mathematics

Combinatorics

46 pages, final version that will appear in Communications in Analysis and Geometry

Scientific paper

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, the neighborhood graph method leads to new estimates for the smallest nontrivial eigenvalue that can improve the Cheeger inequality, 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.

Affiliated with

Also associated with

No associations

Rating

Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplacian does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplacian, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplacian will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-123988