Premium
On the number of subtrees for almost all graphs
Author(s) -
Tomescu Ioan
Publication year - 1994
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240050119
Subject(s) - combinatorics , mathematics , poisson distribution , random graph , lambda , distribution (mathematics) , discrete mathematics , graph , physics , statistics , mathematical analysis , quantum mechanics
In this article it is shown that the number of common edges of two random subtrees of K n having r and s vertices, respectively, has a Poisson distribution with expectation 2λμ if \documentclass{article}\pagestyle{empty}\begin{document}$\mathop {\lim }\limits_{n \to \infty } r/n = \lambda$\end{document} and \documentclass{article}\pagestyle{empty}\begin{document}$\mathop {\lim }\limits_{n \to \infty } s/n = \mu$\end{document} . Also, some estimations of the number of subtrees for almost all graphs are made by using Chebycheff's inequality. © 1994 John Wiley & Sons, Inc.