Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-27T19:21:59.645Z Has data issue: false hasContentIssue false
  • English
  • Français

The lengths of limbs of random trees

Part of: Graph theory

Published online by Cambridge University Press:  26 February 2010

J. W. Moon
J. W. Moon
Affiliation:
University of Cape Town and University of Alberta.
Get access

Extract

A tree is a connected graph that has no cycles. If x is any endnode of a tree, then the limb determined by x is the unique path that joins x with the nearest node other than x that does not have degree two in the tree; let l(x) denote the length of this path. (For definitions and results not given here see [2] or [3].) Different endnodes determine different limbs with one exception; when the tree is a path then both endnodes determine the same limb, namely, the tree itself. Our object here is to investigate the distribution of the length of limbs of trees Tn chosen at random from the set of nn-2 trees with n labelled nodes; in particular, it will follow from our results that the length of the longest limb in most trees Tn is approximately log n when n is large.

MSC classification

Secondary: 05C05: Trees 05C30: Enumeration in graph theory
Type
Research Article
Information
Mathematika , Volume 18 , Issue 1 , June 1971 , pp. 78 - 81
Copyright
Copyright © University College London 1971

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.)

References

1.Bromwich, T. J., An introduction to the theory of infinite series (Macmillan, London, 1931).Google Scholar
2.Moon, J. W., “Counting labelled trees”, Canadian Mathematical Congress, Montreal, 1970.Google Scholar
3.Ore, O., Theory of graphs, Amer. Math. Soc. Colloq. Publ. 38 (Providence, 1962).Google Scholar