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 R 2 ( 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 − 2 2 ⌋ ≤ m ≤ n ( n − 1 ) ) 2 − 1 by applying the Pólya counting principle.