The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph

Combinatorics Probability and Computing - Tập 3 Số 1 - Trang 97-126 - 1994
Svante Janson1
1Department of Mathematics, Uppsala University, PO Box 480, S-751 06, Uppsala, Sweden

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

Bollobás, 1985, Random Graphs

10.1002/rsa.3240030303

Moon, 1967, Graph theory and theoretical physics, 261

Jerrum, 1993, Proceedings of the 3rd conference on Integer Programming and Combinatorial Optimization, 171

10.1007/BF00718031

10.1017/S0305004100066111

[4] Janson S. (1994) Orthogonal decompositions and functional limit theorems for random graph statistics. Mem. Amer. Math. Soc. (to appear).

Thông tin
Thông tin xuất bản

Combinatorics Probability and Computing

Tập 3 Số 1

97-126

Thông tin tác giả