Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 

 

Random trees in random graphs


Authors: E. A. Bender and N. C. Wormald
Journal: Proc. Amer. Math. Soc. 103 (1988), 314-320
MSC: Primary 05C80; Secondary 05C05
MathSciNet review: 938689
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We show that a random labeled $ n$-vertex graph almost surely contains isomorphic copies of almost all labeled $ n$-vertex trees, in two senses. In the first sense, the probability of each edge occurring in the graph diminishes as $ n$ increases, and the set of trees referred to as "almost all" depends on the random graph. In the other sense, the probability of an edge occurring is fixed, and the relevant set of trees is predetermined. The same method applies to show that almost all labeled $ n$-tournaments contain isomorphic copies of almost all labeled oriented $ n$-trees.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C80, 05C05

Retrieve articles in all journals with MSC: 05C80, 05C05


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1988-0938689-5
Article copyright: © Copyright 1988 American Mathematical Society