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?)

  • [1] L. E. Clarke, On Cayley's formula for counting trees, J. London Math. Soc. 33 (1958), 471-474. MR 0100854 (20:7282)
  • [2] P. Erdös and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17-61. MR 0125031 (23:A2338)
  • [3] -, On random matrices. II, Studia Sci. Math. Hungar. 3 (1968), 459-464. MR 0244072 (39:5389)
  • [4] P. Erdös and J. Spencer, Probabilistic methods in combinatorics, Academic Press, New York, 1974. MR 0382007 (52:2895)
  • [5] J. Komlós and E. Szemerédi, Limit distribution for the existence of Hamiltonian cycles in a random graph, Discrete Math. 43 (1983), 55-63. MR 680304 (85g:05124)
  • [6] A. D. Korshunov, Solution of a problem of Erdös and Rényi on Hamiltonian cycles in undirected graphs, Soviet Math. Dokl. 17(3) (1976), 760-764.
  • [7] J. W. Moon, On the maximum degree in a random tree, Michigan Math. J. 15 (1968), 429-432. MR 0233729 (38:2050)
  • [8] K. B. Reid and N. C. Wormald, Embedding oriented $ n$-trees in tournaments, Studia Sci. Math. Hungar. 18 (1983), 377-387. MR 787942 (86i:05075)
  • [9] D. Sumner, private communication with K. B. Reid.
  • [10] N. C. Wormald, Subtrees of large tournaments, Combinatorial Mathematics X, Lecture Notes in Math., Vol. 1036, Springer-Verlag, 1983, pp. 417-419. MR 731598 (85j:05024)

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

Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society