Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-28T14:56:00.880Z Has data issue: false hasContentIssue false
  • English
  • Français

Connectivity of finite anisotropic random graphs and directed graphs

Published online by Cambridge University Press:  24 October 2008

Joel E. Cohen
Joel E. Cohen
Affiliation:
Rockefeller University, New York, NY 10021, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

For graphs on a finite set of vertices with arbitrary probabilities of independently occurring edges, the reliability is defined as the probability that the graph is connected, and the redundancy as the expected number of spanning trees of the graph. Analogous measures of connectivity are defined for random finite directed graphs with arbitrary probabilities of independently occurring directed edges. Recursive formulas for computing the reliability are known. Determinantal formulas, based on matrix-tree theorems, for computing the redundancy are given here. Among random graphs with a given sum of edge probabilities, the more evenly the probabilities are distributed over potential edges, the larger the redundancy. This inequality, proved using the theory of majorization, in combination with examples shows unexpectedly that conflicts between reliability and redundancy can arise in the design of communication networks modelled by such random graphs. The significance of these calculations for the command and control of nuclear forces is sketched.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 99 , Issue 2 , March 1986 , pp. 315 - 330
Copyright
Copyright © Cambridge Philosophical Society 1986

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

REFERENCES

[1]Aitken, A. C.. Determinants and Matrices (9th ed., reprinted) (Oliver and Boyd, 1958).Google Scholar
[2]Austin, T. L., Fagen, R. E., Penny, W. F. and Riordan, J.. The number of components in random linear graphs. Ann. of Math. Stat. 30 (1959), 747–754.CrossRefGoogle Scholar
[3]Biggs, N.. Algebraic Graph Theory (Cambridge University Press, 1974).Google Scholar
[4]Bollobás, B.. Graph Theory: An Introductory Course (Springer-Verlag, 1979).CrossRefGoogle Scholar
[5]Bracken, P.. The Command and Control of Nuclear Forces (Yale University Press, 1983).Google Scholar
[6]Brooks, R. L., Smith, C. A. B., Stone, A. H. and Tutte, W. T.. The dissection of rectangles into squares. Duke Math. J. 7 (1940), 312–340.Google Scholar
[7]Buzacott, J. A.. A recursive algorithm for finding reliability measures related to the connection of nodes in a graph. Networks 10 (1980), 311–327.CrossRefGoogle Scholar
[8]Buzacott, J. A.. A recursive algorithm for directed-graph reliability. Networks 13 (1983), 241–246.CrossRefGoogle Scholar
[9]Carter, A. B.. The command and control of nuclear war. Scientific American 252 (1) (01 1985), 32–39.CrossRefGoogle Scholar
[10]Cvetković, D. M., Doob, M. and Sachs, H.. Spectra of Graphs (Academic Press, 1980).Google Scholar
[11]Dorea, C. C. Y.. Connectivity of random graphs. J. Appl. Probab. 19 (1982), 880–884.Google Scholar
[12]Erdös, P.. The Art of Counting: Selected Writings, ed. Spencer, J. (MIT Press, 1973).Google Scholar
[13]Erdös, P. and Rényi, A.. On random graphs. I. Publ. Math. Debrecen 6 (1959), 290–297.CrossRefGoogle Scholar
[14]Erdös, P. and Rényi, A.. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5 (1960), 17–61.Google Scholar
[15]Erdös, P. and Rényi, A.. On the strength of connectedness of a random graph. Acta Math. Acad. Sci. Hungar. 12 (1961), 261–267.CrossRefGoogle Scholar
[16]Esary, J. D., Proschan, F. and Walkup, D. W.. Association of random variables, with applications. Ann. of Math. Stat. 38 (1967), 1466–74.CrossRefGoogle Scholar
[17]Feller, W.. An Introduction to Probability Theory and its Applications, vol. 1, 3rd ed. (Wiley, 1968).Google Scholar
[18]Gilbert, E. N.. Random graphs. Ann. of Math. Stat. 30 (1959), 1141–1144.CrossRefGoogle Scholar
[19]Grimmett, G. R.. Random fields and random graphs. D.Phil. thesis, University of Oxford 1974.Google Scholar
[20]Grimmett, G. R.. Random graphs. In Selected Topics in Graph Theory, vol. 2, ed. Beineke, L. and Wilson, R.. (Academic Press, 1983), 201–235.Google Scholar
[21]Grimmett, G. R., Keane, M. and Marstrand, J. M.. On the connectedness of a random graph. Math. Proc. Cambridge Philos. Soc. 96 (1984), 151–166.Google Scholar
[22]Harary, F.. Graph Theory (Addison Wesley, 1969).CrossRefGoogle Scholar
[23]Karoński, M.. A review of random graphs. J. Graph Theory 6 (1982), 349–389.CrossRefGoogle Scholar
[24]Kel'mans, A. K.. Some problems of network reliability analysis. [In Russian.] Avtomat. i Telemekh. 26 (3) (1965), 567–574. [English translation: Automat. Remote Control 26 (1965), 564–573.]Google Scholar
[25]Kel'mans, A. K.. On graphs with randomly deleted edges. Acta Math. Acad. Sci. Hungar. 37 (1981), 77–88.CrossRefGoogle Scholar
[26]Marshall, C. W.. Applied Graph Theory (Wiley-Interscience, 1971).Google Scholar
[27]Marshall, A. W. and Olkin, I.. Inequalities: Theory of Majorization and its Applications (Academic Press, 1979).Google Scholar
[28]Provan, J. S. and Ball, M. O.. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12 (1983), 777–788.CrossRefGoogle Scholar
[29]Provan, J. S. and Ball, M. O.. Computing network reliability in time polynomial in the number of cuts. Oper. Res. 32 (1984), 516–526.CrossRefGoogle Scholar
[30]Robinson, D. F. and Foulds, L. R.. Digraphs: Theory and Techniques (Gordon and Breach, 1980).Google Scholar
[31]Ross, S. M.. A random graph. Journal of Applied Probability 18 (1981), 309–315.CrossRefGoogle Scholar
[32]Steinbruner, J.. Launch under attack. Scientific American 250 (1) (01 1984), 37–47.Google Scholar
[33]Stubbs, D. R. and Good, P. I.. Connectivity in random networks. Bull. Math. Biol. 38 (1976), 295–304.CrossRefGoogle ScholarPubMed
[34]Temperley, H. N. V.. On the mutual cancellation of cluster integrals in Mayer's fugacity series. Proceedings of the Physical Society 83 (1964), 3–16.Google Scholar
[35]Trent, H. M.. A note on the enumeration and listing of all possible trees in a connected linear graph. Proc. Nat. Acad. Sci. U.S.A. 40 (1954), 1004–1007.CrossRefGoogle Scholar
[36]Tutte, W. T.. Graph Theory (Addison Wesley, 1984).Google Scholar