Optimal Structures of Random Graphs

This article presents some new results on the optimal structures of random graphs with unreliable edges. It is shown that, in the general case, different structures are optimal when considering different reliability indicators. The graph connection probability (All Terminal Reliability, ATR), the expectation of the number of connected pairs of nodes (EDP), which is one-to-one with the expectation of the number of connected pairs of nodes (ECP) and the average value of the probability of pairwise connectivity (APC). Most of the results are obtained for graphs with equally unreliable edges, but some results are also presented for the general case. We study the problem of optimal placement of “special” edges, that is, edges whose reliability differs significantly from the reliability of the others in the graph. Most of the results presented are for trees and cycles, which are models for a wide variety of real-world networks.