Average Distance in Weighted Graphs with Removed Edges

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 \geq 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 \geq 4\), and for weighted \(K_{3,n}\) and \(K_{2,n}\) graphs for \(n \geq 2\).