The edge-Wiener index of a graph (Q1025981)

The Wiener index \(W(G)\) of a (connected) graph \(G\) is the sum of distances between all pairs of vertices in \(G\). The edge-Wiener index \(W_e(G)\) of \(G\) is the Wiener index of its line graph \(L(G)\), i.e., \(W_e(G)=W(L(G))\). The authors give bounds on \(W_e(G)\) in terms of order and size of \(G\). In particular, they prove that \(W_e(G)\leq \frac{2^2}{5^5} n^5 +O(n^{9/2})\) for all graphs \(G\) of order \(n\) and that the coefficient of \(n^5\) in this upper bound is best possible.