On Wiener inverse interval problem of trees

Jelena Sedlar


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 16n3 + 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 112n3 + O(n5/2), which essentially solves two conjectures posed in the literature.


Wiener index, Wiener inverse interval problem, tree

Full Text:


DOI: https://doi.org/10.26493/1855-3974.1376.7c2

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications