Isoperimetric inequalities, growth, and the spectrum of graphs (Q1111573): Difference between revisions

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.