Judgment Criteria for Reliability Comparison of Three-Terminal Graphs with High Edge Failure Probability
A three-terminal graph is defined as a simple graph comprising three specified target vertices. The reliability of three-terminal graphs represents the probability that these three target vertices remain connected, given that each edge fails independently with a constant probability <i>q</i...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-06-01
|
| Series: | Axioms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2075-1680/14/6/457 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | A three-terminal graph is defined as a simple graph comprising three specified target vertices. The reliability of three-terminal graphs represents the probability that these three target vertices remain connected, given that each edge fails independently with a constant probability <i>q</i>. In this paper, we focus on exploring the characteristics of more reliable three-terminal graphs when the edge failure probability approaches 1. Three reliability comparison criteria are proposed to characterize the locally most reliable three-terminal graph progressively when the number of edges <i>m</i> is in the range of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>[</mo><mn>5</mn><mo>,</mo><mn>4</mn><mi>n</mi><mo>−</mo><mn>10</mn><mo>]</mo></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>[</mo><mfenced separators="" open="(" close=")"><mstyle scriptlevel="0" displaystyle="true"><mfrac linethickness="0pt"><mi>n</mi><mn>2</mn></mfrac></mstyle></mfenced><mo>−</mo><mi>n</mi><mo>+</mo><mn>4</mn><mo>,</mo><mfenced separators="" open="(" close=")"><mstyle scriptlevel="0" displaystyle="true"><mfrac linethickness="0pt"><mi>n</mi><mn>2</mn></mfrac></mstyle></mfenced><mo>]</mo></mrow></semantics></math></inline-formula>. At the same time, the locally optimal structures in the range of the edge number <i>m</i> with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>4</mn><mi>n</mi><mo>−</mo><mn>10</mn><mo>,</mo><mfenced separators="" open="(" close=")"><mstyle scriptlevel="0" displaystyle="true"><mfrac linethickness="0pt"><mi>n</mi><mn>2</mn></mfrac></mstyle></mfenced><mo>−</mo><mi>n</mi><mo>+</mo><mn>4</mn><mo>)</mo></mrow></semantics></math></inline-formula> are restricted to six specific classes of graphs. Furthermore, based on these criteria, a method is introduced to search local optimal structures and offer a theoretical foundation for constructing optimal networks and repairing faulty ones. |
|---|---|
| ISSN: | 2075-1680 |