CYCLES IN RANDOM GRAPHS

被引：11

作者：

LUCZAK, T

机构：

[1] Department of Discrete Mathematics, Adam Mickiewicz University, Poznań

来源：

DISCRETE MATHEMATICS | 1991年 / 98卷 / 03期

关键词：

D O I：

10.1016/0012-365X(91)90379-G

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G(n, p) be a graph on n vertices in which each possible edge is presented independently with probability p = p(n) and upsilon-1(n, p) denote the number of vertices of degree 1 in G(n, p). It is shown that if epsilon > 0 and np(n) --> infinity then the probability that G(n, p) contains cycles of all lengths r, 3 less-than-or-equal-to r less-than-or-equal-to n - (1 + epsilon)upsilon-1(n, p), tends to 1 as n --> infinity.

引用

页码：231 / 236

页数：6

共 7 条

[1]

BOLLOBAS B, 1986, RANDOM GRAPHS

[2]

ERDOS P, 1960, MAGYAR TUD AKAD MAT, V5, P17

[3] ON LARGE MATCHINGS AND CYCLES IN SPARSE RANDOM GRAPHS [J].