Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T23:07:47.040Z Has data issue: false hasContentIssue false
  • English
  • Français

Cycles in a Uniform Graph Process†

Published online by Cambridge University Press:  12 September 2008

Jerzy Jaworski  and
Tomasz Łuczak
Jerzy Jaworski
Affiliation:
Department of Discrete Mathematics, Adam Mickiewicz University, Poznań, Poland.
Tomasz Łuczak
Affiliation:
Department of Discrete Mathematics, Adam Mickiewicz University, Poznań, Poland.
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the asymptotic properties of a “uniform” random graph process in which the minimum degree of U(n, M) grows at least as fast as ⌊M/n⌋. We show that if M — n → → ∞, almost surely U(n, M) consists of one giant component and some number of small unicyclic components. We go on to study the distribution of cycles in unicyclic components as they emerge at the beginning of the process and disappear when captured by the giant one.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 1 , Issue 3 , September 1992 , pp. 223 - 239
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Berg, S. and Jaworski, J. (1992) Probability distributions related to local structure of a random mapping. In: Proceedings of Random Graphs '89, Wiley.Google Scholar
[2]Bollobás, B. (1985) Random Graphs, Academic Press.Google Scholar
[3]Bollobás, B. and Rasmussen, S. (1989) First cycles in random directed graph processes. Discrete Math. 75 55–68.CrossRefGoogle Scholar
[4]Flajolet, P., Knuth, D. E. and Pittel, B. (1989) The first cycle in an evolving graph. Discrete Math. 75 167–216.CrossRefGoogle Scholar
[5]Janson, S. (1987) Poisson convergence and Poisson processes with applications to random graphs. Stock Proc. Appl. 26 1–30.CrossRefGoogle Scholar
[6]Jaworski, J. (1985) Random Mappings, Ph.D. dissertation, Inst.Mat.Uniw.im.A.Mickiewicza Poznań (in Polish).Google Scholar
[7]Jaworski, J. and Mutafchiev, L. (submitted) The largest connected component in a random mapping. Proceedings of Random Graphs ’91, Poznań.Google Scholar
[8]Luczak, T. (1990) Component behaviour near the critical point of the random graph process. Random Structures & Algorithms 1 287–310.CrossRefGoogle Scholar
[9]Pittel, B. (1983) On the distribution related to transitive closures of finite random mappings. Annals of Probability 11 428–41.CrossRefGoogle Scholar
[10]Riordan, J. (1968) Combinatorial Identities, Wiley, New York.Google Scholar