Cycles in a Random Graph Near the Critical Point
Cycles in a Random Graph Near the Critical Point
复制标题
DOI：
10.1002/rsa.3240020405
复制
发表时间：
1991-12
期刊：
影响因子：
--
通讯作者：
T. Luczak
中科院分区：
文献类型：
--
作者：
T. Luczak
设G（n，M）是从所有n阶标号图族中随机选取的一个图，M（n）= 0.5n + s（n），其中s3（n）n−2→∞但s（n）= o（n）.本文给出了G（n，M）的最大分支所含最短圈的长度和最大分支外最长圈的长度的极限分布，描述了G（n，M）的块结构，并由此导出了G（n，M）中含有一个对角圈的极限概率。最后，我们证明了当n → ∞时G（n，M）中最长圈的长度趋于1的概率为s2（n）/n阶.© 1991 Wiley Periodicals，Inc.
Let G(n, M) be a graph chosen at random from the family of all labelled graphs with n vertices and M(n) = 0.5n + s(n) edges, where s3(n)n−2→∞ but s(n) = o(n). We find the limit distribution of the length of shortest cycle contained in the largest component of G(n, M), as well as of the longest cycle outside it. We also describe the block structure of G(n, M) and derive from this result the limit probability that G(n, M) contains a cycle with a diagonal. Finally, we show that the probability tending to 1 as n‐→∞ the length of the longest cycle in G(n, M) is of the order s2(n)/n. © 1991 Wiley Periodicals, Inc.