Graphs with polynomial growth

V. I. Trofimov

Sbornik. Mathematics, Tome 51 (1985) no. 2, pp. 405-417

Résumé

Let $\Gamma$ be a connected locally finite vertex-symmetric graph, $R(n)$ the number of vertices of $\Gamma$ at a distance not more than $n$ from some fixed vertex. The equivalence of the following assertions is proved: (a) $R(n)$ is bounded above by a polynomial; (b) there is an imprimitivity system $\sigma$ with finite blocks of $\operatorname{Aut}\Gamma$ on the set of vertices of $\Gamma$ such that $\operatorname{Aut}\Gamma/\sigma$ is finitely generated nilpotent-by-finite and the stabilizer of a vertex of $\Gamma/\sigma$ in $\operatorname{Aut}\Gamma/\sigma$ is finite. Thus, in a certain sense, a description is obtained of the connected locally finite vertex-symmetric graphs with polynomial growth. Bibliography: 8 titles.