×

zbMATH — the first resource for mathematics

Isoperimetric inequalities, growth, and the spectrum of graphs. (English) Zbl 0658.05055
This article concerns two relatively new graph invariants for an infinite graph G with bounded vertex degrees. The isoperimetric number i(G), is the infimum of \(| \partial X| /| X|\) over all finite sets of vertices X, where \(\partial X\) is the set of edges with just one end in X. If we define \(b(x,n)=| \{u:\quad dist(u,x)\leq n\}\) for each vertex x, then the exponential growth number of x is \(\epsilon (x)=\limsup [b(x,n)]^{1/n},\) and the growth number of G is \(\epsilon (G)=\sup \{\epsilon (x)\}.\) (If G is connected, the exponential growth number is the same for all vertices.)
The author relates these two invariants to the spectral radius of the adjacency matrix (operator), to upper and lower degree bounds, and to each other. Similar relations are given for the transition isoperimetric number, the infimum of \(| \partial X| /S(X),\) X as above, and S(X) the sum of degrees of vertices in X. In some cases, further bounds are given for isoperimetric numbers (suitably defined) of finite graphs. Here, the second largest eigenvalue of the adjacency matrix and the second smallest of the Laplacian matrix enter.
Reviewer: D.Powers

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A42 Inequalities involving eigenvalues and eigenvectors
58E35 Variational inequalities (global problems) in infinite-dimensional spaces
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N., Eigenvalues and expanders, Combinatorica, 6, 83-96, (1986) · Zbl 0661.05053
[2] N. Biggs, B. Mohar, and J. Shawe-Taylor, The spectral radius of infinite graphs, Bull. London Math. Soc., to appear. · Zbl 0671.05052
[3] Cheeger, J., A lower bound for the smallest eigenvalue of the Laplacian, (), 195-199 · Zbl 0212.44903
[4] Dodziuk, J., Difference equations, isoperimetric inequality and transience of certain random walks, Trans. amer. math. soc., 284, 787-794, (1984) · Zbl 0512.39001
[5] J. Dodziuk and W.S. Kendall, Combinatorial Laplacians and isoperimetric inequality, to appear. · Zbl 0619.05005
[6] P. Gerl, Random walks on graphs with a strong isoperimetric property, to appear. · Zbl 0639.60072
[7] Gerl, P.; Woess, W., Simple random walks on trees, European J. combin., 7, 321-331, (1986) · Zbl 0606.05021
[8] B. Mohar, Isoperimetric numbers of graphs, submitted for publication.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.