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


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

  • $\begingroup$ Would you please clarify? $\endgroup$ – Peter Heinig Sep 4 '17 at 17:33
  • 1
    $\begingroup$ 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? : ) $\endgroup$ – Lwins Sep 4 '17 at 17:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Heinig Sep 4 '17 at 18:28
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Heinig Sep 4 '17 at 18:55
  • $\begingroup$ To @PeterHeinig. Thank you! It is definitely clearer than my version. $\endgroup$ – Lwins Sep 4 '17 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.