engleski

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[Tn] the set of all values of the Wiener index for a graph from the class Tn of trees on n vertices. The largest interval of consecutive integers (consecutive even integers in case of odd n) contained in W[Tn] is denoted by Wint[Tn]. In this paper we prove that both sets are of cardinality 1⁄6n3 + O(n5/2) in the case of even n, while in the case of odd n we prove that the cardinality of both sets equals 1⁄12n3 + O(n5/2), which essentially solves two conjectures posed in the literature.

Wiener index ; Wiener inverse interval problem ; tree

nije evidentirano