Take the 2-minute tour ×

Assume you have a simple, infinite graph $G$ with bounded degree (there is an upper bound for the degree of the nodes). Choose an arbitrary vertex $x\in V(G)$ 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.

My question is the following

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.

share|improve this question
In the sentence "The total traffic in $G_n$ is equal to $n(n-1)/2$" and later on you seem to be using $n$ to denote both the radius of the graph and its number of vertices. Could you, please, change the notation? –  Sergey Norin Apr 4 '11 at 20:04
Thanks, I changed it. –  ght Apr 4 '11 at 20:08
It is not clear to me that G_n should have O(n) vertices, much less that the total traffic in G_n should be n choose 2. Can you clarify these points? Also, in the proof of the bound you seek, can you tell us how planarity is used, and what a weaker replacement might be that you are confident would work? Gerhard "Ask Me About System Design" Paseman, 2011.04.04 –  Gerhard Paseman Apr 4 '11 at 20:11
@Gerhard: I did an abuse of notation which I already corrected. I hope it makes sense now. For the proof of the planar case you essentially prove that you can break your graph in two almost equal parts by a path of length $2n$. –  ght Apr 4 '11 at 20:27
The correction helps. For a possible counterexample, I can imagine the initial vertex v_0 being a central locus of a "backwater" of the entire graph, so that for large values of n is looks like traffic collects around v_0, but for even larger values of N, one ties into a vast river of shorter, regularly arranged nodes, so that there will be exponentially many nodes sharing loads, and that things will be distributed by, say, some kind of hypercube architecture. If bounded degree means limited connectvity though, it won't work. Gerhard "Ask Me About System Design" Paseman, 2011.04.04 –  Gerhard Paseman Apr 4 '11 at 20:53

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
I see the problem in your solution. The diameter of $G|S_{k}$ is at most $2(k+\log_{r-1}(k)+C)$. This makes all the difference. –  ght Apr 5 '11 at 16:40
@Gabriel: It would make the difference, but I am not sure where your factor of $2$ comes from. $G|S_k$ has the structure of the $r$-regular graph I am discussing above with $N'=(r−1)^k$. –  Sergey Norin Apr 5 '11 at 16:55
@Norin: I'm sorry, I totally misunderstood your construction. What you are actually doing is joining the notes in $S_{k}(x_0)$ (which has size $(r-1)^k$) via a $r$ regular graph. I thought that you were attaching a $r$ regular graph at each node. Now it makes sense. Thanks! –  ght Apr 5 '11 at 17:33

Your Answer


