The distinguishing feature between a cycle and a torus is that for not too large $d$ the number of vertices at most $d$ steps away from a chosen vertex is $\Omega(d)$ for the cycle and $\Omega(d^2)$ for the torus. Hence the "dimension" $d(G)$ of a graph $G$ may be defined as $\beta$ in the best approximation of the number $\omega_d(G)$ of pairs of vertices at distance at most $d$ with $C n d^\beta$ for $d$ much smaller than the diameter of $G$.

A problem of this definition is that $\omega_d(G)$ may exhibit several regimes of growth for certain graphs. For example, take a $w \times h$ grid graph with $w << h$. Then for $d < w$ we will have $\beta = 2$, but $\beta = 1$ for $w < d < h$. It is not hard to construct a graph that exhibit any given kind of piecewise constant regime of $\beta$. Hence it is hard to name a single number that describes the "dimension" of the graph, but rather the information about "dimension spectrum" is encoded in the sequence $\omega_d(G)$.

One way to distinguish a cycle from a torus is that for not too large $d$ the number of vertices at most $d$ steps away from a chosen vertex is $\Omega(d)$ for the cycle and $\Omega(d^2)$ for the torus. Hence the "dimension" $d(G)$ of a graph $G$ may be defined as $\beta$ in the best approximation of the number $\omega_d(G)$ of pairs of vertices at distance at most $d$ with $C n d^\beta$ for $d$ much smaller than the diameter of $G$.

A problem of this definition is that $\omega_d(G)$ may exhibit several regimes of growth for certain graphs. For example, take a $w \times h$ grid graph with $w << h$. Then for $d < w$ we will have $\beta = 2$, but $\beta = 1$ for $w < d < h$. It is not hard to construct a graph that exhibit any given kind of piecewise constant regime of $\beta$. Hence it is hard to name a single number that describes the "dimension" of the graph, but rather the information about "dimension spectrum" is encoded in the sequence $\omega_d(G)$.

The distinguishing feature between a cycle and a torus is that for not too large $d$ the number of vertices at most $d$ steps away from a chosen vertex is $\Omega(d)$ for the cycle and $\Omega(d^2)$ for the torus. Hence the "dimension" $d(G)$ of a graph $G$ may be defined as $\beta$ in the best approximation of the number $\omega_d(G)$ of pairs of vertices at distance at most $d$ with $C n d^\beta$.

The distinguishing feature between a cycle and a torus is that for not too large $d$ the number of vertices at most $d$ steps away from a chosen vertex is $\Omega(d)$ for the cycle and $\Omega(d^2)$ for the torus. Hence the "dimension" $d(G)$ of a graph $G$ may be defined as $\beta$ in the best approximation of the number $\omega_d(G)$ of pairs of vertices at distance at most $d$ with $C n d^\beta$ for $d$ much smaller than the diameter of $G$.

A problem of this definition is that $\omega_d(G)$ may exhibit several regimes of growth for certain graphs. For example, take a $w \times h$ grid graph with $w << h$. Then for $d < w$ we will have $\beta = 2$, but $\beta = 1$ for $w < d < h$. It is not hard to construct a graph that exhibit any given kind of piecewise constant regime of $\beta$. Hence it is hard to name a single number that describes the "dimension" of the graph, but rather the information about "dimension spectrum" is encoded in the sequence $\omega_d(G)$.