A network structure with $ n $ vertices and $ m $ edges is practically represented by a graph with $ n $ vertices and $ m $ edges. The graph with $ k $ fixed target vertices is called a $ k $-terminal graph. This article studies the locally most reliable simple sparse three-terminal graphs, in which each edge survives independently with probability $ p $. For $ p $ close to $ 0 $ or $ 1 $, the locally most reliable three-terminal graphs with $ n $ vertices and $ m $ edges are determined, where $ n\geq5 $ and $ 9\leq m\leq4n-10 $. Finally, we prove that there is no uniformly most reliable three-terminal graph for $ n\geq5 $, $ 11 < m \leq3n-5 $ and $ m\equiv 2(\bmod 3) $ and for $ n\geq7 $, $ 3n-5 < m \leq4n-10 $. This research provides helpful guidance for constructing a highly reliable network with three target vertices.
Citation: Sun Xie, Haixing Zhao, Liming Dai, Jun Yin. On locally most reliable three-terminal graphs of sparse graphs[J]. AIMS Mathematics, 2021, 6(7): 7518-7531. doi: 10.3934/math.2021439
A network structure with $ n $ vertices and $ m $ edges is practically represented by a graph with $ n $ vertices and $ m $ edges. The graph with $ k $ fixed target vertices is called a $ k $-terminal graph. This article studies the locally most reliable simple sparse three-terminal graphs, in which each edge survives independently with probability $ p $. For $ p $ close to $ 0 $ or $ 1 $, the locally most reliable three-terminal graphs with $ n $ vertices and $ m $ edges are determined, where $ n\geq5 $ and $ 9\leq m\leq4n-10 $. Finally, we prove that there is no uniformly most reliable three-terminal graph for $ n\geq5 $, $ 11 < m \leq3n-5 $ and $ m\equiv 2(\bmod 3) $ and for $ n\geq7 $, $ 3n-5 < m \leq4n-10 $. This research provides helpful guidance for constructing a highly reliable network with three target vertices.
| [1] |
J. I. Brown, D. Cox, Nonexistence of optimal graphs for all terminal reliability, Networks, 63 (2014), 146–153. doi: 10.1002/net.21530
|
| [2] |
H. Bertrand, O. Goff, C. Graves, M. Sun, On uniformly most reliable two-terminal graphs, Networks, 72 (2018), 200–216. doi: 10.1002/net.21811
|
| [3] |
F. T. Boesch, X. Li, C. Suffel, On the existence of uniformly optimal networks, Networks, 21 (1991), 181–194. doi: 10.1002/net.3230210204
|
| [4] | J. A. Bondy, U. S. R. Murty, Graph Theory, Berlin: Springer, 2008. |
| [5] |
O. D. Byer, Two path extremal graphs and an application to a Ramsey-type problem, Discrete Math., 196 (1999), 51–64. doi: 10.1016/S0012-365X(98)00195-2
|
| [6] |
Y. N. Chen, Z. S. He, Bounds on the reliability of distributed systems with unreliable nodes & links, IEEE T. Reliab., 53 (2004), 205–215. doi: 10.1109/TR.2004.829152
|
| [7] | H. Z. Chi, D. K. Li, A $K$-tree algorithm for computing $K$-terminal reliability in networks, J. Northeast Univ. Technol., 14 (1993), 424–428. |
| [8] |
T. Evans, D. Smith, Optimally reliable graphs for both edge and vertex failures, Networks, 16 (1986), 199–204. doi: 10.1002/net.3230160208
|
| [9] |
O. Goldschmidt, P. Jaillet, R. Lasota, On reliability of graphs with node failures, Networks, 24 (1994), 251–259. doi: 10.1002/net.3230240407
|
| [10] |
D. Gross, J. T. Saccoman, Uniformly optimally reliable graphs, Networks, 31 (1998), 217–225. doi: 10.1002/(SICI)1097-0037(199807)31:4<217::AID-NET2>3.0.CO;2-G
|
| [11] | X. M. Li, Current status and trends in the synthesis of reliable networks, Chin. J. Comput., 13 (1990), 699–705. |
| [12] | S. B. Liu, K. H. Cheng, X. P. Liu, Network reliability with node failures, Networks, 35 (2015), 109–117. |
| [13] | L. Cui, Y. F. Xiao, Factorization realizing approximate estimation of 2-terminal networks reliability, Comput. Eng. Appl., 48 (2012), 53–57. |
| [14] |
W. Myrvold, K. H. Cheung, L. B. Page, J. E. Perry, Uniformly-most reliable networks do not always exist, Networks, 21 (1991), 417–419. doi: 10.1002/net.3230210404
|
| [15] | Y. F. Niu, Y. H. Wang, X. Z. Xu, New decomposition algorithm for computing two-terminal network reliability, Comput. Eng. Appl., 47 (2011), 79–82. |
| [16] | P. Romero, Building uniformly most-reliable networks by iterative augmentation, 2017 9th International Workshop on Resilient Networks Design and Modeling (RNDM), 2017, 1–7. |
| [17] | F. Simon, Splitting the $K$-terminal reliability, Mathematics, 2011. |
| [18] |
A. Satyanarayana, M. K. Chang, Network reliability and the factoring theorem, Networks, 13 (1983), 107–120. doi: 10.1002/net.3230130107
|
| [19] |
J. Silva, T. Gomes, D. Tipper, L. Martins, V. Kounev, An effective algorithm for computing all-terminal reliability bounds, Networks, 66 (2015), 282–295. doi: 10.1002/net.21634
|
| [20] |
L. G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput., 8 (1979), 410–421. doi: 10.1137/0208032
|
| [21] |
G. F. Wang, A proof of Boesch's conjecture, Networks, 24 (1994), 277–284. doi: 10.1002/net.3230240504
|
| [22] |
M. Wang, Q. Li, Conditional edge connectivity properties, reliability comparisons and transitivity of graphs, Discrete Math., 258 (2002), 205–214. doi: 10.1016/S0012-365X(02)00299-6
|
| [23] | Y. P. Wang, X. L. Su, An algorithm for computing $K$-terminal reliability of undirected network with ramdom edges, J. Beijing Univ. Posts Telecommun., 17 (1994), 48–53. |
| [24] | H. Zhang, L. C. Zhao, L. Wang, H. J. Sun, An new algoirhtm of computing $K$-terminal network reliability, Sci. Technol. Eng., 5 (2005), 387–390. |
Figures(5) / Tables(1)
Sun Xie, Haixing Zhao, Liming Dai, Jun Yin. On locally most reliable three-terminal graphs of sparse graphs[J]. AIMS Mathematics, 2021, 6(7): 7518-7531. doi: 10.3934/math.2021439
DownLoad: