Son gráficos con escasa $r$-bolas necesariamente escasos?

Question

Deje $G$ ser una ponderada de grafo no dirigido con la siguiente propiedad:

Para algunos entero $r$, para todos los nodos $v$, tenemos $$\frac{\sum \limits_{u \in B(v, r)} \deg(u)}{|B(v, r)|} \le D$$ donde $B(v, r) = \{u \, | \, \mathop{dist}(u, v) \le r\}$.

¿Esto implica que $|E(G)| = O(nD)$?

El reclamo es trivialmente cierto para $r=0$ o $r = \mathop{rad}(G)$. Esto también es cierto para $r=1$ (ver Brendan McKay agradable comentario más abajo).

Answer 1

Me he decidido a publicar mi argumento pero de todos modos, ya que nadie (incluyendo el OP) expresado ningún interés, sólo voy a esbozar las pruebas. Voy a suponer también que $r\ge 2$.

Parte 1. El límite superior de La condición implica inmediatamente que $$ \sum_{y\in B(x,r)}d(y)\le D|B(x,r)|\le D\sum_{y\in B(x,r-1)}d(y) $$ Vamos ahora a $\sigma(x)=\sum_{y\in B(x,r)}d(y)$. Si $x$ e $z$ son adyacentes, entonces $$ \sigma(x)\le D\sum_{y\in B(x,r-1)}d(y)\le D\sigma(y) $$ sólo porque $B(x,r-1)\subset B(y,r)$. De ello se deduce inmediatamente que, para cualquier $y\in B(x,r)$, tenemos $$ D^{-r}\sigma(x)\le \sigma(y)\le D^r\sigma(x)\,. $$ Ahora se multiplican las desigualdades $\sum_{y\in B(x,r)}d(y)\le D|B(x,r)|$ por $d(x)/\sigma(x)$ agregar y cambiar el orden de la suma. Tenemos $$ \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)} $$ La sustitución de $\sigma(x)$ por $\sigma(y)$ sólo puede crear un multiplicativo de error $D^r$ en cada lado, por lo que finalmente consigue $$ 2|E|=\sum_y d(y)\le D^{2r+1}\sum_y 1=D^{2r+1}|V| $$

Parte 2. Un ejemplo de crecimiento de la energía. Considere la red de carreteras que consta de un ciclo de $ABCDEFA$ y un extra de camino de $BF$ donde todos los $7$ caminos de longitud $1$ cada uno. Hacer los caminos $AF$ e $AB$ carreteras de peaje con el uniforme de peaje $7/3$ por unidad de longitud de los caminos $DC$ e $DE$ carreteras de peaje con el uniforme de peaje $4/3$ por unidad de longitud, y el resto de las carreteras libres. A continuación, para cada bola de radio $2$ en la métrica del espacio construido, el total de peaje asociado con la pelota, no exceda el total de la longitud de la carretera asociados con ella (ella es suficiente para comprobar las bolas centradas en las ciudades debido a que ambas funciones son lineales en cada camino), pero el total de muertos es $22/3$, que es estrictamente mayor que el total de la longitud de la carretera. Tomando un gran $r$, poniendo sobre la $r/2$ extra de pueblos a lo largo de cada camino, y soltando los peajes, sólo un poco, vamos a tener un gráfico y una función de $g$ en los vértices con las propiedades de $\sum_{y\in B(x,r)g(y)}\le |B(x,r-1)|$ por cada $x$ pero $\sum_y g(y)>(1+\delta)|V|$. Observar también que tenemos $|B(x,r)|\le (1+Cr^{-1})|B(x,r-1)|$. Ahora toma el $n$-ésima potencia de la gráfica de la elección de $n$, de modo que $(1+Cr^{-1})^n\approx D$, elija un enorme $U$ y adjuntar a cada vértice $x=(x_1,\dots,x_n)$ $U$ vértices de grado $1$ y un grafo completo con $\sqrt{g(x_1)\dots g(x_n)U}$ vértices.