Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-05T02:10:19.905Z Has data issue: false hasContentIssue false
  • English
  • Français

Connectivity of random graphs

Published online by Cambridge University Press:  14 July 2016

Chang C. Y. Dorea
Chang C. Y. Dorea*
Affiliation:
Universidade de Brasilia
*
∗ Permanent address: Depto de Matemática-IE, Universidade de Brasilia, 70910 Brasilia DF, Brazil. From 1982 to 1984 the author will be a Visiting Scholar at Iowa State University.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a random field {Xij, i, j = 1, ···, n} where the random variables Xij takes on values 1 or 0. The collection {Xij } can be viewed as a random graph with nodes {1, ···, n} by interpreting X ij = 1 as the existence of an arc emanating from the node i to the node j. Such a representation will enable us to study ordered and unordered graphs, being also the general representation of a random graph. In this note the probability that the graph is connected is computed under the condition that ΣiXki=l for k = 1, · ··, n. This result extends Ross's recent theorems on connectivity of random graphs.

Keywords

RANDOM FIELDSPROBABILITY OF CONNECTIVITY
Type
Short Communications
Information
Journal of Applied Probability , Volume 19 , Issue 4 , December 1982 , pp. 880 - 884
Copyright
Copyright © Applied Probability Trust 1982 

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] Busacker, R. G. and Saaty, T. L. (1965) Finite Graphs and Networks: an Introduction with Applications. McGraw-Hill, New York.Google Scholar
[2] Harris, B. (1960) Probability distributions related to random mappings. Ann. Math. Statist. 31, 1045–1062.Google Scholar
[3] Ross, S. M. (1981) A random graph. J. Appl. Prob. 18, 309–315.Google Scholar