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$
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.