首页 | 本学科首页   官方微博 | 高级检索  
     


Cycles in a random graph near the critical point
Authors:Tomasz Luczak
Abstract: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.
Keywords:
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号