Wiener Index - Inverse Problem

Inverse Problem

Gutman & Yeh (1995) considered the problem of determining which numbers can be represented as the Wiener index of a graph. They showed that all but two positive integers have such a representation; the two exceptions are the numbers 2 and 5, which are not the Wiener index of any graph. For graphs that must be bipartite, they found that again almost all integers can be represented, with a larger set of exceptions: none of the numbers in the set

{2, 3, 5, 6, 7, 11, 12, 13, 15, 17, 19, 33, 37, 39}

can be represented as the Wiener index of a bipartite graph.

Gutman and Yeh conjectured, but were unable to prove, a similar description of the numbers that can be represented as Wiener indices of trees, with a set of 49 exceptional values. The conjecture was later proven by Wagner, Wang, and Yu.