Question

Assume you have a simple, infinite graph with bounded degree (there is an upper bound for the degree of the nodes). Choose $x$ an arbitrary vertex and consider $$ G_{n}:=\{x\in G:d(x_0,x)\leq n\} $$ with the graph metric (hop metric). Assume that each pair of nodes is communicating a unit load of information and the load goes through the minimum path between nodes (if there is more than one minimum path we choose one arbitrarily). The total traffic in $G_{n}$ is equal to $\frac{N(N-1)}{2}$ where $N=N(n)=|G_{n}|$.

Given a node $v\in G_{n}$ we define $T_{n}(v)$ as the total traffic generated in $G_{n}$ passing through $v$. In other words, $T_{n}(v)$ is the sum off all the geodesic paths in $G_{n}$ which are carrying traffic and contain the node $v$.

If the graph $G$ is planar and it has exponential growth $|G_{n}|=K\exp(\lambda n)$ for $n$ sufficiently large, then it is not difficult to prove that there are nodes in $G_{n}$ such that $$ T_{n}(v)\geq C\frac{N^2}{\log(N)} $$ for $n$ sufficiently large.

Is the same true if we remove the planar condition but we keep the exponential growth? My intuition is that the answer is no but I can't find a counterexample.

Answer 1

I think the following provides a counterexample.

The idea is to use the fact that on a graph $G$ with maximum degree $\Delta$ and diameter $D$ reasonably close to the natural lower bound $\log_{\Delta-1}|V(G)|$ the traffic is almost uniformly distributed.

Explicitly, for a vertex $v$, let $S_k(v):=\{x \in V(G) \: | \: d(x,v)=k\}$. Then $|S_k(v)| \leq \Delta(\Delta-1)^{k-1}$ and the traffic through $v$ can be estimated as $$T_G(v) \leq \sum_{k+l \leq D} |S_k(v)||S_l(v)| < D^2\Delta^2(\Delta-1)^{D-2}.$$

Bollobas and de la Vega in a paper "The diameter of random regular graphs" (last reference for Lecture 1 at the link.) show that for sufficiently large $N'$ a random $r$-regular graph on $N'$ vertices has diameter at most $\log_{r-1}(N') + \log_{r-1}(\log_{r-1}(N'))+C$, where $C$ is a (small) constant depending on $r$. By adjusting $C$, we may assume that an $r$-regular graph on $N'$ vertices satisfying this bound on diameter exists for any $N'$.

Finally, we construct $G$ by, first, taking an infinite $r$-regular tree, except that for simplicity of calculations we let the degree of $x_0$ be $r-1$. Secondly, we put an $r$-regular graph with the diameter bound listed above on the set of vertices $S_k(x_0)$, that is on each level of our infinite tree, considered as rooted at $x_0$.

Note that $|S_k(x_0)|=(r-1)^k$ and the diameter of $G|S_k(x_0)$ (i.e. $G$ restricted to $S_k(x_0)$) is at most $k + \log_{r-1}(k)+C$. It follows that the diameter of $G_n$ is at most $$\max_{k \leq l \leq n}( \mathrm{diam}(G|S_k(x_0)) + l-k) \leq n + \log_{r-1}(n)+C$$

The graph $G_n$ has maximum degree $\Delta = 2r$ and by the bound on the traffic load above we have $$ T_n(v) \leq n^2(2r-1)^{n+\log_{r-1}(n)+C'}$$ for any $v \in V(G_n)$ and some choice of $C'(r)$ independent on $n$. On the other hand $$|V(G_n)|=N =\sum_{k=0}^n (r-1)^k > (r-1)^n$$

It follows that, for any $\epsilon >0$ we can choose large enough $r$ so that for large $n$ we have $T_n(v) \leq N^{1 + \epsilon}$ for every $v \in G_n$.