In this talk, we give estimates for the largest eigenvalue of the normalized graph Laplacian which measures how close to bipartite a graph is. It is well known that the largest eigenvalue is at least n/(n-1) where n is the number of vertices and equality is attained only for the complete graph. We show that for all non-complete graphs, the largest eigenvalue is at least (n+1)/(n-1) and we characterize equality. We later got to know that the same result was already proven in a very different way in "Extremal Graph on Normalized Laplacian Spectral Radius and Energy", The Electronic Journal of Linear Algebra. However, our result suggests the definition of a Cheeger constant for the largest eigenvalue purely in terms of the smallest vertex degree.

 

海报