Extremely Optimal Graph Research for Network Reliability

Network reliability refers to a probabilistic measure of a network system’s ability to maintain its intended service functionality within a specified time interval and under given operating conditions. Let Ω(n,m) be the set of all simple two-terminal networks on n vertices and m edges. If each edge operates independently with the same fixed probability p∈[0,1], then the two-terminal reliability, denoted by R2(G,P)), is the probability that there exists a path between two target vertices s and t. For a given number of vertices n and edges m, there are some graphs within Ω(n,m) that have higher reliability than others, and these are known as extremely optimal graphs. In this work, we determine the sets of extremely optimal graphs in two classes of two-terminal network with sizes m=n(n−1))2−2 and m=n(n−1))2−3, consisting of 2 and 5 networks, respectively. Moreover, we identify one class of graphs obtained by deleting some edges among non-target vertices in the complete two-terminal graph, and we count the number of graphs of this class with size n(n−1)2−⌊n−22⌋≤m≤n(n−1))2−1 by applying the Pólya counting principle.