On Cheeger‐type inequalities for weighted graphs
- 22 July 2002
- journal article
- Published by Wiley in Journal of Graph Theory
- Vol. 41 (1) , 1-17
Abstract
We give several bounds on the second smallest eigenvalue of the weighted Laplacian matrix of a finite graph and on the second largest eigenvalue of its weighted adjacency matrix. We establish relations between the given Cheeger‐type bounds here and the known bounds in the literature. We show that one of our bounds is the best Cheeger‐type bound available. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 1–17, 2002Keywords
This publication has 10 references indexed in Scilit:
- Lower bounds for the eigenvalues of Laplacian matricesLinear Algebra and its Applications, 2000
- On the second real eigenvalue of nonegative and Z-matricesLinear Algebra and its Applications, 1997
- Some applications of Laplace eigenvalues of graphs1997
- An estimate for the nonstochastic eigenvalues of doubly stochastic matricesLinear Algebra and its Applications, 1995
- Degree maximal graphs are Laplacian integralLinear Algebra and its Applications, 1994
- Laplace eigenvalues of graphs—a surveyDiscrete Mathematics, 1992
- Lower bounds for the first eigenvalue of certain M-matrices associated with graphsLinear Algebra and its Applications, 1992
- Isoperimetric numbers of graphsJournal of Combinatorial Theory, Series B, 1989
- Isoperimetric inequalities, growth, and the spectrum of graphsLinear Algebra and its Applications, 1988
- Eigenvalues and expandersCombinatorica, 1986