Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T03:39:45.487Z Has data issue: false hasContentIssue false

On the total heights of random rooted trees

Part of:Graph theory

Published online by Cambridge University Press:  14 July 2016

Lajos Takacs*
Affiliation:
Case Western Reserve University
*
∗ Postal address: 2410 Newbury Drive, Cleveland Heights, OH 44118, USA.

Abstract

Denote by Sn the set of all distinct rooted trees with n labeled vertices. Define τn as the total height of a tree chosen at random in the set Sn , assuming that all the possible nn –1 choices are equally probable. The total height of a tree is defined as the sum of the heights of its vertices. The height of a vertex in a rooted tree is the distance from the vertex to the root of the tree, that is, the number of edges in the path from the vertex to the root. This paper is concerned with the distribution and the moments of τn and their asymptotic behavior as n → ∞.

MSC classification

Primary:05C05: Trees

Information

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 1992 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable