WIENER-TYPE INVARIANTS OF TREES AND THEIR RELATION

Abstract

The distance d(u, v|G) between the vertices u and v of a (con-nected) graph G is the length ( = number of edges) of a shortest path connecting u and v. The Wiener number W (G) of G is the sum of distances between all pairs of vertices of G. We consider a class of Wiener–type invariants Wλ(G) , defined as the sum of the terms d(u, v|G)λ over all pairs of vertices of G. Several special cases of Wλ(G) , namely the invariants for λ = +1 (the original Wiener number) as well as for λ = −2,−1,+1/2,+2 and +3, were previ-ously studied in the chemical literature, and found applications as molecular structure descriptors. We modify the definition of Wλ(G) so that it extends also to non-connected graphs and then deduce the identity Wλ+1(T) = (n − 1)Wλ(T) − Wλ(T − e) , valid for any n-vertex tree T, with the summation embracing all edges e of T. 1 1