# Estimates for the drop in the sum of all pairwise weighted distances effected by a decrease of the weight of an edge

Consider simple connected undirected graphs $G = (V, E)$ equipped with a function $w\colon E\rightarrow \{x\in \mathbb{R}\colon x\geq 0\}$.

Define a function $d_{G,w}\colon V\times V\rightarrow\mathbb{R}$ by $d_{G,w}(u,v):=\inf\{\sum_{e\in E(P)} w(e) \colon \text{$P$a graph-theoretic$u$-$v$-path}\}$.

The (dual of the) least-upper-bound property implies that the function $d_{G,w}$ always exists for any data as above, in particular for infinite $G$.

If $V$ (and hence $E$) is finite, let

$D_{G,w}:=\sum_{(u,v)\in V\times V} d_{G,w}(u,v)$.

Then:

Let $w(e) \geq 1$ for all $e \in E$. If $V$ (and hence $E$) is finite, then for each $e\in E$, and with $w-e\colon E\rightarrow\{x\in \mathbb{R}\colon x\geq 0\}$ denoting the function given by $(w-e)(e)=w(e)-1\geq 0$ and $(w-e)(e')=e'$ for all other $e'$, we have $$D_{G,w} \geq D_{G,w-e} \geq D_{G,w} - \frac{1}{2}|V|^2\ .$$

It could be proved by noticing that the decrement could not contribute to $(u,v)$, if contributing to $(u,w)$ and $(v,t)$ in whose shortest path $u$ and $v$ are linked to the same endpoint (node) of $e$, respectively. However I have not rigidly checked the proof.

I wonder whether researchers have done work on this (or similar operations).

To summarize: is there work on, roughly speaking, the set of all pairwise distances varies when edge-weights are being decremented? (It is not necessary that this work is concerned exactly with the function $D_{G,w}$, similar notions would be helpful too, e.g., $D'_{G,w}:=\sum_{(u,v)\in V\times V} \exp(d_{G,w}(u,v))$)

By the way, here is a funny conjecture coming from myself. I have not considered it in detail so do not be serious about it.

Let $w(e)=1$ for all $e \in E$. If $V$ (and hence $E$) is finite, then for each $F = \{e_1, \dots, e_k\} \subseteq E$, and with $w-F\colon E\rightarrow\{x\in \mathbb{R}\colon x\geq 0\}$ denoting the function given by $(w-F)(e)=0$ for $e \in F$ and $(w-F)(e')=1$ for all other $e' \in E - F$, we have $$D_{G,w-F}/D_{G,w} \geq \Omega(\log_{|V|}k).$$

P.S. The bound given by the first proposition is tight. An infinite set of examples is given by letting $G$ be the even-order graph obtained from the disjoint union of two complete graphs of equal order $s$, with one additional edge added between the two, and weigth $1$ on each edge. If the bridge-edge has its weight decremented, then the quantity $D_{G,w}$ decreases by exactly $2\cdot s^2 = 2\cdot(\frac12\lvert V\rvert)^2 = \frac12\lvert V\rvert^2$.

• Would you please clarify? – Peter Heinig Sep 4 '17 at 17:33
• To @PeterHeinig. Thanks for your comment. I have edited the OP and I hope it is now clear. However I am unable to comprehend your statement about $D_G$. Could you please explain it in more detail? : ) – Lwins Sep 4 '17 at 17:42
• Thanks for clarifying. I was reading and writing in a rush. Your are right with your comment and your claim that the bound is tight. The simplest non-trivial example, as you say, is the graph consisting of two vertex-disjoint triangles with one additional edges between them, weight 1 on each edge, and the decrement happening on the bridge-edge. Then, your function $D_G$ drops by exactly $2\cdot (\frac12\lvert V\rvert)^2=\frac12\lvert V\rvert^2$, achieving your lower bound. – Peter Heinig Sep 4 '17 at 18:28
• I did an extensive rewrite of your question. If you have reasons to object, please re-edit. I think it is significantly better this way. – Peter Heinig Sep 4 '17 at 18:55
• To @PeterHeinig. Thank you! It is definitely clearer than my version. – Lwins Sep 4 '17 at 18:57