Connectivity of finite anisotropic random graphs and directed graphs
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.
- A NOTE ON THE ENUMERATION AND LISTING OF ALL POSSIBLE TREES IN A CONNECTED LINEAR GRAPH
- A random graph
- A recursive algorithm for finding reliability measures related to the connection of nodes in a graph
- A review of random graphs
- Algebraic Graph Theory
- Association of Random Variables, with Applications
- Connectivity in random networks
- Connectivity of random graphs
- scientific article; zbMATH DE number 3760195 (Why is no real title available?)
- scientific article; zbMATH DE number 3450155 (Why is no real title available?)
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- scientific article; zbMATH DE number 3358495 (Why is no real title available?)
- Inequalities: theory of majorization and its applications
- On graphs with randomly deleted edges
- On the strength of connectedness of a random graph
- Random Graphs
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- The dissection of rectangles into squares
- The Number of Components in Random Linear Graphs
- Note on directed proper connection number of a random graph
- Connectivity of soft random geometric graphs over annuli
- The Central Limit Theorem and the Law of Large Numbers for Pair-Connectivity in Bernoulli Trees
- Graphs with given connectivity properties
- Connectivity in random forests and credit networks
- Random Accessibility as a Parallelism to Reliability Studies on Simple Graphs
- On connectivity and robustness of random graphs with inhomogeneity
- Connectivity and dynamics for random subgraphs of the directed cube
This page was built for publication: Connectivity of finite anisotropic random graphs and directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3742403)