Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



A random graph with a subcritical number of edges

Author: B. Pittel
Journal: Trans. Amer. Math. Soc. 309 (1988), 51-75
MSC: Primary 05C80
MathSciNet review: 957061
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A random graph $ {G_n}(\operatorname{prob} (\operatorname{edge} ) = p)\;(p = c/n,\,0 < c < 1)$ on $ n$ labelled vertices is studied. There are obtained limiting distributions of the following characteristics: the lengths of the longest cycle and the longest path, the total size of unicyclic components, the number of cyclic vertices, the number of distinct component sizes, and the middle terms of the component-size order sequence. For instance, it is proved that, with probability approaching $ {(1 - c)^{1/2}}\exp (\sum\nolimits_{j = 1}^l {{c^j}/2j)} $ as $ n \to \infty $, the random graph does not have a cycle of length $ > l$. Another result is that, with probability approaching $ 1$, the size of the $ \nu $th largest component either equals an integer closest to $ a\;\log (bn/\nu \,{\log ^{5/2}}n)$, $ a = a(c)$, $ b = b(c)$, or is one less than this integer, provided that $ \nu \to \infty $ and $ \nu = o(n/{\log ^{5/2}}n)$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C80

Retrieve articles in all journals with MSC: 05C80

Additional Information

Article copyright: © Copyright 1988 American Mathematical Society