17
$\begingroup$

Let $G$ be an unweighted undirected graph with the following property:

For some integer $r$, for all nodes $v$, we have $$\frac{\sum \limits_{u \in B(v, r)} \deg(u)}{|B(v, r)|} \le D$$ where $B(v, r) = \{u \, | \, \mathop{dist}(u, v) \le r\}$.

Does this imply that $|E(G)| = O(nD)$?

The claim is trivially true for $r=0$ or $r = \mathop{rad}(G)$. It is also true for $r=1$ (see Brendan McKay's nice comment below).

$\endgroup$
  • 7
    $\begingroup$ For $r=1$, write it as $\sum_{u\in B(v,1)} \deg(u) \le D (\deg(v)+1)$ and sum over all $v$. Apply the fact that the root-mean-square of a set of positive numbers is at most equal to the average. It gives that the average degree in the whole graph is at most $D$ with equality iff the graph is $D$-regular. $\endgroup$ – Brendan McKay Oct 2 '15 at 2:11
  • $\begingroup$ $O(nD)$ is overly optimistic. The right bound is about $O(D^{cr}n)$ (linear in $n$, but only power in $D$ with the power proportional to $r$). Let me know if anyone still interested. :-) $\endgroup$ – fedja Apr 7 '17 at 17:05
4
$\begingroup$

I've decided to post my argument anyway but, since nobody (including the OP) expressed any interest, I'll just sketch the proofs. I shall also assume that $r\ge 2$.

Part 1. The upper bound The condition immediately implies that $$ \sum_{y\in B(x,r)}d(y)\le D|B(x,r)|\le D\sum_{y\in B(x,r-1)}d(y) $$ Let now $\sigma(x)=\sum_{y\in B(x,r)}d(y)$. If $x$ and $z$ are adjacent, then $$ \sigma(x)\le D\sum_{y\in B(x,r-1)}d(y)\le D\sigma(y) $$ just because $B(x,r-1)\subset B(y,r)$. It follows immediately that for any $y\in B(x,r)$, we have $$ D^{-r}\sigma(x)\le \sigma(y)\le D^r\sigma(x)\,. $$ Now multiply the inequalities $\sum_{y\in B(x,r)}d(y)\le D|B(x,r)|$ by $d(x)/\sigma(x)$ add them up and change the order of summation. We get $$ \sum_y d(y)\sum_{x\in B(y,r)}\frac{d(x)}{\sigma(x)}\le D\sum_y\sum_{x\in B(y,r)}\frac{d(x)}{\sigma(x)} $$ Replacing $\sigma(x)$ by $\sigma(y)$ can only create a multiplicative error $D^r$ on each side, so we finally get $$ 2|E|=\sum_y d(y)\le D^{2r+1}\sum_y 1=D^{2r+1}|V| $$

Part 2. An example of power growth. Consider the road network consisting of a cycle $ABCDEFA$ and an extra road $BF$ where all $7$ roads have length $1$ each. Make the roads $AF$ and $AB$ toll roads with uniform toll $7/3$ per unit length, the roads $DC$ and $DE$ toll roads with uniform toll $4/3$ per unit length, and the remaining roads free. Then for every ball of radius $2$ in the metric space just constructed, the total toll associated with that ball does not exceed the total road length associated with it (it is enough to check it for balls centered at the towns because both functions are linear on each road) but the total toll is $22/3$, which is strictly larger than the total road length. Taking a large $r$, putting about $r/2$ extra towns along each road, and dropping the tolls just a tiny bit, we shall get a graph and a function $g$ on vertices with the properties $\sum_{y\in B(x,r)g(y)}\le |B(x,r-1)|$ for every $x$ but $\sum_y g(y)>(1+\delta)|V|$. Observe also that we have $|B(x,r)|\le (1+Cr^{-1})|B(x,r-1)|$. Now take the $n$-th power of that graph choosing $n$ so that $(1+Cr^{-1})^n\approx D$, choose a huge $U$ and attach to each vertex $x=(x_1,\dots,x_n)$ $U$ vertices of degree $1$ and a complete graph with $\sqrt{g(x_1)\dots g(x_n)U}$ vertices.

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