Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T09:39:05.300Z Has data issue: false hasContentIssue false

Random trees in a graph and trees in a random graph

Published online by Cambridge University Press:  24 October 2008

Svante Janson
Affiliation:
Department of Mathematics, Uppsala University, Sweden
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.

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.

Information

Type
Research Article
Copyright
Copyright © Cambridge Philosophical Society 1986