Return to Revisions

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