Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-28T05:10:15.207Z Has data issue: false hasContentIssue false
  • English
  • Français

On nodes of degree two in random trees

Published online by Cambridge University Press:  26 February 2010

A. Meir  and
J. W. Moon
A. Meir
Affiliation:
The University of Alberta, Edmonton.
J. W. Moon
Affiliation:
The University of Alberta, Edmonton.
Get access

Extract

Let T(n, k) denote the number of trees n with n labelled nodes of which exactly k have degree two. We shall derive a formula for T(n, k) and then determine the asymptotic behaviour of T(n,0); this will enable us to calculate the limiting distribution of Xn the number of nodes of degree two in a random tree n. Rényi [5] has treated the corresponding problem for nodes of degree one in random trees.

Type
Research Article
Information
Mathematika , Volume 15 , Issue 2 , December 1968 , pp. 188 - 192
Copyright
Copyright © University College London 1968

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.Cayley, A., “A theorem on trees”, Quart. J. Math., 23 (1897), 376–378.Google Scholar
2.Feller, W., An introduction to probability theory and its applications I (Wiley, New York, 1957).Google Scholar
3.Harary, F. and Prins, G., “The number of homeomorphically irreducible trees and other species”, Acta Mathematica, 101 (1959), 141–162.CrossRefGoogle Scholar
4.Moon, J. W., “Various proofs of Cayley's formula for counting trees”, A seminar on graph theory, edited by Harary, F. (Holt, Rinehart, and Winston, New York, 1967), 70–78.Google Scholar
5.Rényi, A., “Some remarks on the theory of trees”, Publi. Math. Inst. Hung. Acad. Sci., 4 (1959), 73–85.Google Scholar