Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T14:10:11.305Z Has data issue: false hasContentIssue false

Cutting down random trees

Published online by Cambridge University Press:  09 April 2009

A. Meir
Affiliation:
The University of AlbertaEdmonton, Alberta, Canada
J. W. Moon
Affiliation:
The University of AlbertaEdmonton, Alberta, Canada
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let Tn denote a tree with n(≧ 2) labelled points: we assume Tn is rooted at a given point x, say the point labelled 1 (see [3] for definitions not given here). If we remove some edge e of Tn, then Tn falls into two subtrees one of which, say Tk, contains the root x. If k ≧ 2 we can remove some edge of Tk and obtain an even smaller subtree of Tn that contains x. If we repeat this process we will eventually obtain the subtree consisting of x itself. Let λ = λ(Tn) denote the number of edges removed from Tn before the root x is isolated. Our main object here is to determine the expected value μ(n) and variance σ2(n) of λ(Tn) under the assumptions (1) Tn is chosen at random from the set of nn−2 trees with n labelled points that are rooted at point x, and (2) at each stage the edge removed is chosen at random from the edges of the remaining subree containing x. It follows from our results that μ(n) ~ (½πn)½ and (2−½π)n ~ (2−½π)n as n tends to infinity. We also consider the corresponding problem for forests of rooted trees and for trees in which the degree of the root is specified. We are indebted to Professor Alistair Lachlan for suggesting the original problem to us.

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1970

References

[1]Cayley, A., ‘A theorem on trees’, Quart. J. Math. 23 (1889), 376378. Collected papers, Cambridge, 13 (1897), 26–28.Google Scholar
[2]Clarke, L. E., ‘On Cayley's formula for counting trees’, J. London Math. Soc. 33 (1958), 471475.CrossRefGoogle Scholar
[3]Ore, O., Theory of Graphs, (American Math. Soc. Colloq. Publi. 38, Providence, 1962).Google Scholar
[4]Pólya, G. and Szegö, G., Aufgaben und Lehrsätze aus der Analysis, Bd. 1 (Springer-Verlag, Berlin, Aufg. 3, 1964).Google Scholar
[5]Rényi, A., ‘Some remarks on the theory of trees’, Publi. Math. Inst. Hung. Acad. Sci. 4 (1959), 7385.Google Scholar