Construction of graph with given Wiener Index

Question

Given the sum of weights of shortest paths between all vertices in a graph, how can I construct a connected graph that satisfies the given sum? That is, how can a graph with a given wiener index be created?

Answer 1

This question is addressed on the Wikipedia page Wiener index. Gutman, Yeh and Chen showed that there are no (unweighted) graphs with Wiener index 2 or 5, but all other values are attainable. In a subsequent paper, Gutman and Yeh determine which Wiener indices are attainable on bipartite graphs, and on the way explain how to prove the earlier result, an explanation which we reiterate here.

Consider the clique on $n$ vertices. Its Wiener index is $\binom{n}{2}$. Pick a vertex $v$ from the clique. Suppose we remove $m$ edges $(x_1,y_1),\ldots,(x_m,y_m)$ not adjacent to $v$. Since $x_i,y_i$ are connected via $v$, each edge we remove increases the Wiener index by one, and so the resulting Wiener index is $\binom{n}{2} + m$. The maximal number of edges we can remove is $\binom{n-1}{2}$, which corresponds to a Wiender index of $\binom{n}{2} + \binom{n-1}{2} = (n-1)^2$. We deduce that for every $n$, there are graphs having Wiener index $\frac{n(n-1)}{2}$ to $(n-1)^2$. Let's list these ranges for small $n$, starting with $n = 2$: $$ [1,1], \; [3,4], \; [6,9], \; [10,16], \; [15,25], \ldots $$ Denoting the intervals as $[a_n,b_n]$, starting with $n=5$ we have $a_{n+1} < b_n$, which is not hard to check directly. Therefore, in this way we can construct graphs of any Wiener index other than $2$ or $5$.

It remains to rule out 2 and 5. First, note that a graph of $n$ vertices has Wiener index at least $\binom{n}{2}$. Since $\binom{4}{2} = 6$, it is enough to consider all graphs on at most 3 vertices:

1. A path of length 1 has Wiener index 1.
2. A triangle has Wiener index 3.
3. A path of length 2 has Wiener index 4.

These are the only connected graphs on at most 3 vertices.