3
$\begingroup$

Let $G = (V,E)$ a graph, equipped with graph distance (i.e. for $x,y \in V$, the distance $d(x,y)$ is the length of the minimum path connecting $x$ and $y$). For $x \in V$ and $r \in \mathbb N$, define $B(x,r)$ as the ball centered ad $x$ with radius $r$: $$ B(x,r) = \{ y \in V \ :\ d(x,y) \le r \} .$$

I would like to know if there is a common name for the following property, for a fixed integer $D$:

D-dimensional growth: the number of vertices in $B(x,r)$ scales at most as $(1+r)^D$: $$ \exists c>0 \text{ s.t.} \quad \left| B(x,r) \right| \le c (1+r)^D \quad \forall r \in \mathbb N .$$

As a consequence, any such graph must have degree less than $c 2^D$. The converse is not true: take the binary tree as the simplest counter-example.

(Of course, any graph with $| V | \le 2^D$ will verify this property. But I am interested in "large" graphs, not in trivial cases.)

$\endgroup$

1 Answer 1

3
$\begingroup$

Yes, there is a common name for such graphs -- they are called graphs with polynomial growth. See e.g.

W. Imrich, N. Seifter: A survey on graphs with polynomial growth, Discr. Math. 95 (1991), 101-117, http://www.math.uni-hamburg.de/home/diestel/books/directions/imrich-seifter.pdf

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .