Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-27T18:51:27.691Z Has data issue: false hasContentIssue false
  • English
  • Français

On the connectedness of a random graph

Published online by Cambridge University Press:  24 October 2008

G. R. Grimmett ,
M. Keane  and
J. M. Marstrand
G. R. Grimmett
Affiliation:
School of Mathematics, University of Bristol, England
M. Keane
Affiliation:
Department of Mathematics and Informatics, Delft University of Technology, The, Netherlands
J. M. Marstrand
Affiliation:
School of Mathematics, University of Bristol, England
Get access Rights & Permissions [Opens in a new window]

Abstract

Let p = (p(i): i ≥ 0) be a sequence of numbers satisfying 0 ≤ p(i) < 1 for i = 0,1,2,…, and let G be a random graph with vertex set ℤ = {…, — 1, 0, 1,…} and with edge set defined as follows: for each pair i, j of vertices, where i ≤ j, there is an edge joining i and j with probability p(j — i), independently of the presence or absence of all other edges. We explore the connectedness of G, showing that G is almost surely connected if and only if Σip(i) = ∞ and the (positive) greatest common divisor of the set {i ≥ 1: p(i) < 0} equals 1; if one of these two conditions fails to hold then G is almost surely disconnected. Corresponding results hold in higher dimensions, for random graphs defined on the vertex sets ℤd where d ≥ 2.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 96 , Issue 1 , July 1984 , pp. 151 - 166
Copyright
Copyright © Cambridge Philosophical Society 1984

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] Bollobás, B.. Graph Theory, an Introductory Course (Springer-Verlag, 1979).Google Scholar
[2] Doob, J. L.. Stochastic Processes (John Wiley, 1953).Google Scholar
[3] Grimmett, G. R.. Random graphs: In Selected Topics in Graph Theory 2, ed. Beineke, L. and Wilson, R. (Academic Press, 1983), pp. 201–235.Google Scholar
[4] Holmes, R. A.. Random graphs with the natural numbers as vertices, unpublished manuscript, 1975.Google Scholar
[5] Marstrand, J. M.. Packing smooth curves in ℝa. Mathematika 26 (1979), 1–12.Google Scholar