0
2. 11. 2017.
On Wiener inverse interval problem of trees
The Wiener index W ( G ) of a simple connected graph G is defined as the sum of distances over all pairs of vertices in a graph. We denote by W [ T n ] the set of all values of the Wiener index for a graph from the class T n of trees on n vertices. The largest interval of consecutive integers (consecutive even integers in case of odd n ) contained in W [ T n ] is denoted by W int [ T n ]. In this paper we prove that both sets are of cardinality 1 ⁄ 6 n 3 + O ( n 5/2 ) in the case of even n , while in the case of odd n we prove that the cardinality of both sets equals 1 ⁄ 12 n 3 + O( n 5/2 ), which essentially solves two conjectures posed in the literature.