Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-29T19:03:31.920Z Has data issue: false hasContentIssue false
  • English
  • Français

Random trees in a graph and trees in a random graph

Published online by Cambridge University Press:  24 October 2008

Svante Janson
Svante Janson
Affiliation:
Department of Mathematics, Uppsala University, Sweden
Get access Rights & Permissions [Opens in a new window]

Extract

This paper treats two related sets of problems in the theory of random graphs. In Sections 2 and 3 we study random spanning subtrees of a complete graph (or, equivalently, random labelled trees). It is shown that the number of common edges of two such random trees asymptotically has a Poisson distribution with expectation 2. Similar results are obtained for the number of edges in the intersection or union of more than two random trees.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 100 , Issue 2 , September 1986 , pp. 319 - 330
Copyright
Copyright © Cambridge Philosophical Society 1986

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

REFERENCES

[1] Barbour, A. D. and Eagleson, G. K.. Poisson convergence for dissociated statistics. J. Roy. Statist. Soc. Ser. B 46 (1984), 397–402.Google Scholar
[2] Cayley, A.. A theorem on trees. Quart. J. Math. 23 (1889), 376–378.Google Scholar
[3] Feller, W.. An Introduction to Probability Theory and its Applications I, 3rd ed. (Wiley, 1968).Google Scholar
[4] Ford, G. W. and Uhlenbeck, G. E.. The theory of linear graphs with applications to the virial development of the properties of gases. Studies in Statistical Mechanics I (North-Holland, 1962), 119–211.Google Scholar
[5] McGinley, W. G. and Sibson, R.. Dissociated random variables. Math. Proc. Cambridge Philos. Soc. 77 (1975), 185–188.CrossRefGoogle Scholar
[6] Moon, J. W.. The second moment of the complexity of a graph. Mathematika 11 (1964), 95–98.Google Scholar
[7] Moon, J. W.. Enumerating labelled trees. Graph theory and theoretical physics (ed. Harary, F.) (Academic Press, 1967), 261–272.Google Scholar