Cogrowth of regular graphs
Sam Northshield · Proceedings of the American Mathematical Society · 1992
Let G \mathcal {G} be a d d -regular graph and T T the covering tree of G \mathcal {G} . We define a cogrowth constant of G \mathcal {G} in T T and express it in terms of the first eigenvalue of the Laplacian on G \mathcal {G} . As a corollary, we show that the cogrowth constant is as large as possible if and only if the first eigenvalue of the Laplacian on G \mathcal {G} is zero. Grigorchuk’s criterion for amenability of finitely generated groups follows.