The total Steiner k-distance for b-ary recursive trees and linear recursive trees
Götz Olaf Munsonius
Abstract
We prove a limit theorem for the total Steiner k-distance of a random b-ary recursive tree with weighted edges. The total Steiner k-distance is the sum of all Steiner k-distances in a tree and it generalises the Wiener index. The limit theorem is obtained by using a limit theorem in the general setting of the contraction method. In order to use the contraction method we prove a recursion formula and determine the asymptotic expansion of the expectation using the so-called Master Theorem by Roura (2001). In a second step we prove a transformation of the total Steiner k-distance of b-ary trees with weighted edges to arbitrary recursive trees. This transformation yields the limit theorem for the total Steiner k-distance of the linear recursive trees when the parameter of these trees is a non-negative integer.
Full Text: PostScript PDF