Average Distance in Weighted Graphs with Removed Edges

Abstract

The average distance in a connected weighted graph $G$ is defined as the average of the distances between the vertices of $G$. In 1985 P.M. Winkler [5] conjectured that every connected graph $G$ contains an element $e$, such that the removal of $e$ enlarges the average distance by at most the factor $\frac{4}{3}$.

D. Bienstock and E. Gyéri proved Winkler’s conjecture for the removal of an edge from a connected (unweighted) graph that has no vertices of degree one, and asked whether this conjecture holds for connected weighted graphs. In this paper we prove that any $h$-edge-connected weighted graph contains an edge whose removal does not increase the average distance by more than a factor of $\frac{h}{h-1}$, $h\ge 2$. This proves the edge-case of Winkler’s Conjecture for $4$-connected weighted graphs.

Furthermore, for $3$-edge-connected weighted graphs, it has been verified that the four-thirds conjecture holds for every weighted wheel $W_p$, $p\ge 4$, and for weighted $K_{3,n}$ and $K_{2,n}$ graphs for $n\ge 2$.