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: | |
|
|