This paper examines the distances between vertices in a rooted k-tree, for a fixed k, by exhibiting a correspondence with a variety of trees that can be specified in terms of combinatorial specifications. Studying these trees via generating functions, we show a Rayleigh limiting distribution for expected distances between pairs of vertices in a random k-tree: in a k-tree on n vertices, the proportion of vertices at distance d = X(n~(1/2)) from a random vertex is asymptotic to ((c_k)~2x)/n~(1/2)), where C_k = kH_k.
展开▼
