Connectivity of finite anisotropic random graphs and directed graphs (Q3742403)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3978020
Language Label Description Also known as
default for all languages
No label defined
    English
    Connectivity of finite anisotropic random graphs and directed graphs
    scientific article; zbMATH DE number 3978020

      Statements

      Connectivity of finite anisotropic random graphs and directed graphs (English)
      0 references
      0 references
      1986
      0 references
      graphs on a finite set of vertices
      0 references
      Recursive formulas for computing the reliability
      0 references
      random graphs
      0 references
      reliability and redundancy
      0 references
      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.
      0 references

      Identifiers