Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-22T02:10:57.177Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Altitude of Nodes in Random Trees

Published online by Cambridge University Press:  20 November 2018

A. Meir  and
J. W. Moon
A. Meir
Affiliation:
University of A Iberta, Edmonton, Alberta
J. W. Moon
Affiliation:
University of A Iberta, Edmonton, Alberta
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 nodes that is rooted at node r. (For definitions not given here see [4] or [10].) The altitude of a node u in Tn is the distance α = α (u, Tn) between r and u in Tn. The width of Tn at altitude is the number Wk = Wk(Tn) of nodes at altitude in Tn, where = 0, 1, …

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 30 , Issue 5 , 01 October 1978 , pp. 997 - 1015
Copyright
Copyright © Canadian Mathematical Society 1978

References

1. Bender, E. A., Asymptotic methods in enumeration, SIAM Review 16 (1974), 485–515.Google Scholar
2. Cayley, A., On the analytical forms called trees, Philosophical Magazine 28 (1858), 374-378. Collected Mathematical Papers, Cambridge, 4 (1891), 112–115.)Google Scholar
3. Darboux, G., Mémoire sur l'approximation des fonctions de très grands nombres, et sur une classe étendu de développements en série, Journal de Math. Pures et Appliquées (3) 4 (1878), 5–56.Google Scholar
4. Harary, F. and Palmer, E., Graphical enumeration (Academic Press, New York, 1973).Google Scholar
5. Harary, F., Robinson, R. W., and Schwenk, A. J., Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc. 20 (1975), 483–503.Google Scholar
6. Knuth, D. E., The art of computer programming, III (Addison-Wesley, Reading, 1973).Google Scholar
7. Meir, A. and Moon, J. W., The distance between points in random trees, J. Comb. Theory 8 (1970), 99–103.Google Scholar
8. Meir, A. and Moon, J. W., The expected node-independence number of various types of trees, Recent Advances in Graph Theory (Academia, Prague, 1975), 351–363.Google Scholar
9. Meir, A. and Moon, J. W., Packing and covering constants for certain families of trees, I, J. Graph Theory 1 (1977), 157–174.Google Scholar
10. Moon, J. W., Counting labelled trees (Canadian Mathematical Congress, Montreal, 1970).Google Scholar
11. Moon, J. W., The distance between nodes in recursive trees, Proceedings of the British Combinatorial Conference, 1973 (Cambridge, 1974), 125–132.Google Scholar
12. Otter, R., The number of trees, Ann. of Math. 49 (1948), 583–599.Google Scholar
13. Palmer, E. M. and Schwenk, A. J., On the number of trees in a random forest (abstract), A.M.S. Notices 23 (1976), A-2.Google Scholar
14. Pôlya, G., Kombinatorische Anzahlbestimmungen fur Gruppen, Graphen und chemische Verbindungen, Acta Mathematica 68 (1937), 145–254.Google Scholar
15. Stepanov, V. E., On the distribution of the number of vertices in strata of a random tree, Th. Prob. and its Appl. 14 (1969), 65–78.Google Scholar
16. Volosin, Ju. M., Enumeration of the terms of object domains according to the depth of embedding, Sov. Math. Dokl. 15 (1974), 1777–1782.Google Scholar