JAMC

Article http://dx.doi.org/10.26855/jamc.2023.06.007

Uniformly Optimal Condition of Incomplete Graphs for k-target Graphs Based on Node Unreliability

Download PDF How to cite this paper

TOTAL VIEWS: 3179

Huajiang Qian, Lingbo Jin, Fangming Shao^*

Department of Mathematics, East China University of Science and Technology, Shanghai, China.

*Corresponding author: Fangming Shao

Published: July 30,2023

Abstract

In this paper, we consider the reliability problems of k-target graphs in the case that each non-target node k-target graphs fails independently with the same fixed probability and edges and target nodes are perfectly reliable. The k-target node reliability is the probability that the target nodes are in the same connected component in the induced subgraph of all operational nodes. A k-target graph is uniformly most reliable if, for all node-failure probabilities q∈(0,1), its k-target node reliability is greater than or equal to that of all other k-target graphs with the same fixed number of nodes and edges. We find that in the graph class without a complete bipartite graph K(k,n-k) as its subgraph, the k-target uniformly optimal situation does not always exist. In the graph class Ω(n,n-1), if the number of target nodes meets with k≥2, there must be a k-target uniformly optimal graph, in which its basic connected set has only a single node. It is the same as in the graph class Ω(n,m), when k>n-k and m<2k. In the graph class Ω(n,n), when 2<k≤n-k, there is no k-target uniformly optimal graph. H_k is optimal graph as p→1 and the graph, in which BCS is a single node set, is optimal graph as p→0. In the graph class Ω(n,m), when k=2, the reliability of all graphs in the graph class Ω(n,n) is same.

Keywords

Network reliability, k-target nodes graph, node reliability, k-targe uniformly optimal, uniformly optimal graph, complete bipartite graph

References

[1] I. Brown, C. Graves, B. Miller, et al. Most reliable two-terminal graphs with node failures, Networks, 76(2020), 414-426.

[2] C. Stivaros, On the residual node connectedness network reliability model, PhD Dissertation, Dept. of Electrical Engineering and Computer Science, SIT (1990).

[3] O. Goldschmidt, P. Jaillet, and R. LaSota, On reliability of graphs with node failures, Networks 24 (1994), 251–259.

[4] S. Liu, K. Cheng, and X. Liu, Network reliability with node failures, Networks 35 (2000), 109–117.

[5] S.M. Yu, F.M. Shao and H.J. Meng. Uniformly optimal graphs in some classes of graphs with node failures. Discrete Mathematica 310(2010), 159-166.

[6] Z. Zhang, W. An, F. Shao. Cascading Failures on Reliability in Cyber-Physical System. IEEE Transactions on Reliability, 65(2016), 1745-1754.

[7] F.T. Boesch, X. Li, and C. Suﬀel, On the existence of uniformly optimal networks, Networks 21 (1991), 181-194.

[8] K. Archer, C. Graves, and D. Milan, Classes of uniformly most reliable graphs for all terminal reliability, Discrete Applied Mathematica (2019), 267.

[9] J. Brown and D. Cox, Nonexistence of optimal graphs for all terminal reliability, Networks 63 (2014), 146-153.

[10] A.K. Kelmans, On graphs with randomly deleted edges, Acta Mathematica Academiae Scientiarum Hungaricae, 37 (1981), 77-88.

[11] L. Petingi, J. Saccoman and L. Schoppmann, Uniformly least reliable graphs, Networks, 27 (1996) 125–131.

[12] W. Myrvold, K. Cheung, L. Page, J. Perry, Uniformly-most reliable networks do not always exist, Networks, 21 (1991) 417–419.

[13] Z. Zhang, F. Shao, N. Zhang, et al. Maximizing k-Terminal Network Reliability in Some Sparse Graphs. IEEE/ACM Transactions on Networking, 29(2021) 192-202.

[14] L. Jin. The k-objective consistent optimal problem based on point unreliability and its application, East China University of Science and Technology (2021).

[15] J. I. Brown, D. Cox, and R. Ehrenborg, The average reliability of a graph, Discrete Applied Mathematics, 177(2014) 19-33.

[16] S. Jelena and S. Riste, Vertex and edge metric dimensions of unicyclic graphs, Discrete Applied Mathematics, 314(2022) 81-92.

How to cite this paper

Uniformly Optimal Condition of Incomplete Graphs for k-target Graphs Based on Node Unreliability

How to cite this paper: Huajiang Qian, Lingbo Jin, Fangming Shao. (2023) Uniformly Optimal Condition of Incomplete Graphs for k-target Graphs Based on Node Unreliability. Journal of Applied Mathematics and Computation, 7(2), 257-266.

DOI: http://dx.doi.org/10.26855/jamc.2023.06.007