Extremely Optimal Graph Research for Network Reliability

Zhaoyang Wang and Zhonglin Ye ()
Additional contact information
Zhaoyang Wang: School of Computer, Qinghai Normal University, Xining 810016, China
Zhonglin Ye: State Key Laboratory of Tibetan Intelligent, Qinghai Normal University, Xining 810008, China

Mathematics, 2025, vol. 13, issue 18, 1-13

Abstract: 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.

Keywords: two-terminal network; two-terminal reliability; extremely optimal graph; reliability polynomial (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/18/3000/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/18/3000/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:18:p:3000-:d:1751206

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().