Article contents
The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph
Published online by Cambridge University Press: 12 September 2008
Abstract
The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph Gnm are shown to be asymptotically normal if m is neither too large nor too small. At the lowest limit m ≍ n3/2, these numbers are asymptotically log-normal. For Gnp, the numbers are asymptotically log-normal for a wide range of p, including p constant. The same results are obtained for random directed graphs and bipartite graphs. The results are proved using decomposition and projection methods.
- Type
- Research Article
- Information
- Copyright
- Copyright © Cambridge University Press 1994
References
[2]Frieze, A. and Suen, S. (1992) Counting the number of Hamilton cycles in random digraphs, Random Struct. Alg. 3, 235–241.CrossRefGoogle Scholar
[3]Janson, S. (1986) Random trees in a graph and trees in a random graph, Math. Proc. Camb. Phil. Soc. 100, 319–330.CrossRefGoogle Scholar
[4]Janson, S. (1994) Orthogonal decompositions and functional limit theorems for random graph statistics. Mem. Amer. Math. Soc. (to appear).CrossRefGoogle Scholar
[5]Jerrum, M. (1993) An analysis of a Monte Carlo algorithm for estimating the permanent. Proceedings of the 3rd conference on Integer Programming and Combinatorial Optimization, CORE, Louvain-la-Neuve, Belgium171–182.Google Scholar
[6]Moon, J. W. (1967) Enumerating labelled trees. In: Harary, F. (ed.) Graph theory and theoretical physics, Academic Press, London, 261–272.Google Scholar
[7]Ruciński, A. (1988) When are small subgraphs of a random graph normally distributed? Prob. Th. Rel. Fields. 78, 1–10.CrossRefGoogle Scholar
- 38
- Cited by