The Wiener index of a graph is the sum of the lengths of the shortest paths between all pairs of its vertices.
Are there useful graph-theoretic properties of this index?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
On the same page there was a section: relation to chemical properties (http://en.wikipedia.org/wiki/Wiener_index#Relation_to_chemical_properties) Maybe references in that section mentions more about how this index can be used for graphs. Seems like you can estimate the overall structure of the graph if it is dense (low index) or sparse. Because the lengths of all shortest pairs would be shorter in a dense graph.
-
$\begingroup$ Thanks, I was able to upper bound the average path length of graphs I'm looking at, which is linear in the number of vertices regardless if it is sparse or dense. $\endgroup$ – Ryan Oct 13 '14 at 20:18
$\begingroup$
$\endgroup$
From the abstract of: Dobrynin, Andrey A., Roger Entringer, and Ivan Gutman. "Wiener index of trees: theory and applications." Acta Applicandae Mathematica 66, no. 3 (2001): 211-249
The Wiener index W is the sum of distances between all pairs of vertices of a (connected) graph. The paper outlines the results known for W of trees: methods for computation of W and combinatorial expressions for W for various classes of trees, the isomorphism–discriminating power of W, connections between W and the center and centroid of a tree, as well as between W and the Laplacian eigenvalues, results on the Wiener indices of the line graphs of trees, on trees extremal w.r.t. W, and on integers which cannot be Wiener indices of trees. A few conjectures and open problems are mentioned, as well as the applications of W in chemistry, communication theory and elsewhere.
So, at least for trees, it seems that the Wiener index seems to be related to certain graph-theoretic properties.
