The Wiener index W(G) of a connected graph G is the sum of all of the distances between pairs of vertices of G. This index was introduced in 1947 by the chemist Harry Wiener for studying structure-property relations of hydrocarbons and other organic compounds. Since then, it has been studied extensively by chemists and mathematicians, especially for trees.
This paper extends the study of Wiener indices to those of simply generated trees. In this connection, a simply generated family of trees is defined by a sequence Mk (k ≥ 0) of nonnegative numbers (with M0 > 0); each ordered tree T is given a weight &Pgr;vMd(v), where v ranges over the vertices of T and d(v) is the out-degree of v. The corresponding simply generated random tree Tn is defined by choosing a tree of order n, with probability proportional to its weight (provided that there is some tree of order n with positive weight). Such simply generated random trees (except for some extreme cases not usually considered) are the same as the random conditioned Galton-Watson trees obtained as the family tree of a Galton-Watson process conditioned on a given total size. More precisely, suppose that the generating function M(z) := &Sgr;kMkzk converges, for some z > 0, and that X is an integer-valued random variable with the distribution P(X= k) = MkzkM(z). Then, the conditioned Galton-Watson tree given by the offspring distribution X coincides with the simply generated tree defined by Mk = P(X= k), regardless of the choice of z. Conversely, given a conditioned Galton-Watson tree with an offspring distribution X, we can take Mk = P(X= k). Furthermore, let R ≤ ∞ be the radius of convergence of M(z). Usually, it is assumed that there exists a &OHgr; with 0 < &OHgr; < R and &OHgr;M(&OHgr;) = M(&OHgr;). If z is taken to be &OHgr;, this is equivalent to EX = 1, which leads to a critical Galton-Walton tree.
The paper obtains asymptotics for the mean, variance, and higher moments, as well as for the distribution of the Wiener index of a random tree from a simply generated family or, equivalently, a critical Galton-Walton tree. In addition, a joint asymptotic distribution of the Wiener index and the internal path length is established, as well as asymptotics for the covariance and other mixed moments. The limit laws are described using functionals of a Brownian excursion. The methods include both Aldous’ theory of the continuum random tree, and the analysis of generating functions.