All but 49 Numbers are Wiener Indices of Trees

The Wiener index is one of the main descriptors that correlate a chemical compound’s molecular graph with experimentally gathered data regarding the compound’s characteristics. A long standing conjecture on the Wiener index ([ 4 , 5 ]) states that for any positive integer n (except numbers from a given 49 element set), one can find a tree with Wiener index n . In this paper, we prove that every integer n >10 8 is the Wiener index of some short caterpillar tree with at most six non-leaf vertices. The Wiener index conjecture for trees then follows from this and the computational results in [ 8 ] and [ 5 ].