# Uniformly Most Reliable Three-Terminal Graph of Dense Graphs

Authors: Sun Xie; Haixing Zhao; Jun Yin
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

A graphG with k specified target vertices in vertex set is a k-terminal graph. The k-terminal reliability is the connection probability of the fixed k target vertices in a k-terminal graph when every edge of this graph survives independently with probability p. For the class of two-terminal graphs with a large number of edges, Betrand, Goff, Graves, and Sun constructed a locally most reliable two-terminal graph for p close to 1 and illustrated by a counterexample that this locally most reliable graph is not the uniformly most reliable two-terminal graph. At the same time, they also determined that there is a uniformly most reliable two-terminal graph in the class obtained by deleting an edge from the complete graph with two target vertices. This article focuses on the uniformly most reliable three-terminal graph of dense graphs with n vertices and m edges. First, we give the locally most reliable three-terminal graphs of n and m in certain ranges for p close to 0 and 1. Then, it is proved that there is no uniformly most reliable three-terminal graph with specific n and m, where n≥7 and n2−⌊n−3/2⌋≤m≤n2−2. Finally, some uniformly most reliable graphs are given for n vertices and m edges, where 4≤n≤6 and m=n2−2 or n≥5 and m=n2−1.


---

## Body

## 1. Introduction

Network reliability is a hot topic which has been generally investigated using graph theoretic models. Network withn vertices and m edges can be modeled as a graph G with the same number of vertices, edges, and interconnections as the network. For all-terminal reliability (connection probability of all vertices of a graph), lots of authors investigate the existence of a uniformly most reliable (all-terminal) graph for various values of n and m [1–8]. However, the research on k-terminal reliability (connection probability of k target vertices in a graph, where 2≤k<n) is mainly about the algorithm of computing the k-terminal reliability polynomial [9–13], but only a few results on the construction of the uniformly most reliable k-terminal graph.In [8], Kelmans has shown that for n2−⌊n/2⌋≤m≤n2−2, the uniformly most reliable graph is a complete graph with a matching removed (the matching of a graph is a set of edges with no common vertices between each other). In fact, the design of the real network often only needs to ensure the connectivity of k2≤k<n critical vertices (target vertices). Therefore, the construction of the most reliable k-terminal graph has high application value. There are a few studies on the construction of the most reliable k-terminal structure. In [14], Betrand et al. proved that there is no uniformly most reliable two-terminal graph when n2−⌊n−2/2⌋≤m≤n2−2. At the same time, they also proved that when m=n2−1, the uniformly most reliable two-terminal graph is a complete graph with removing an edge between nontarget vertices. It is natural to consider the following problems.Problems: for the three-terminal graphs with a large number of edges, is there a uniformly most reliable graph? If it exists, what is its construction? If it does not exist, can we construct the locally most reliable three-terminal graph?With these questions, we further study the existence of uniformly most reliable three-terminal graphs for largem. It is difficult to find the exact cases that three target vertices are connected, which is NP-complete [15]. In this paper, we just consider the uniformly most reliable three-terminal dense graphs. In Section 2, some related basic definitions and notations are given. In Section 3, the locally most reliable three-terminal graphs for given m are determined. We show that there is no uniformly most reliable three-terminal graph for n vertices and m edges where n≥7 and n2−⌊n−3/2⌋≤m≤n2−2 and give the uniformly most reliable graphs for 4≤n≤6 and m=n2−2. In Section 4, a uniformly most reliable three-terminal graph with n≥5 vertices and m=n2−1 edges is determined. The results are summarized in Section 5.


## 2. Basic Concepts and Notations

For notations and terminologies not defined here, we refer to [16]. Let βGH denote the number of subgraphs which is isomorphic to H in G. The complement of G, denoted by G¯, is the graph obtained by deleting the edges of G and adding edges between all nonadjacent vertices in G. If u,v∈VG, then G∪uv denotes the addition of the edge uv to G, and G−uv denotes the deletion of the edge uv from G. The union of simple graphs G and H, denoted by G∪H, is the graph with vertex set VG∪VH and edge set EG∪EH. Let Pn be the path with n vertices, Kn be the complete graph with n vertices, and Sn be a star with n vertices and n−1 edges.A graphG with three specified target vertices r,s, and t in VG is a three-terminal graph. Using Gn,m denotes the set of all simple three-terminal graphs with n vertices and m edges. The connectivity probability of the three specified target vertices r,s,t in graph G∈Gn,m when each edge of G survives independently with a fixed probability p is called the three-terminal reliability of G (or the three-terminal reliability polynomial of G), denoted by R3G;p. A v1,v2,…,vj-subgraph is a subgraph of G in which vertices v1,v2,…,vj are connected in the subgraph. In particular, if the v1,v2,…,vj-subgraph with i edges does not contain any v1,v2,…,vj-subgraph with less than i edges, then it is minimal; otherwise, it is nonminimal. Clearly, rst-subgraph is a subgraph of G in which three target vertices r,s,andt are connected in the subgraph. Similar to the definition of two-terminal reliability [14], the three-terminal reliability polynomial of the graph G∈Gn,m can be written as(1)R3G;p=∑i=2mNiGpi1−pm−i,where NiG (or simply Ni) is the number of rst-subgraphs of graph G with i edges.Similar as the definitions of the uniformly most reliable two-terminal graph [14] and the locally most reliable all-terminal graph [3], we defined the uniformly most reliable graph and the locally most reliable graph for three-terminal graphs.Definition 1.
A graphG is the uniformly most reliable graph in Gn,m, if R3G;p≥R3H;p for all H∈Gn,m and all 0≤p≤1. In particular, for p0=0 (or 1), if there is an ε>0 such that R3G;p≥R3H;p for all H∈Gn,m and for all p∈0,1∩p0−ε,p0+ε, then G is the locally most reliable graph in Gn,m for p close to 0(or for p close to 1).Example 1.
Figure1 shows all types of simple three-terminal graph in G4,4 with three target vertices r,s,andt. Each edge of these graphs survives independently with probability p.
InG1, the rst-subgraphs with 2 edges are rs,rt, rs,st,andrt,st, and the rst-subgraphs with 3 edges are rs,rt,st, rs,rt,sv4, rs,st,sv4, and rt,st,sv4, while the rst-subgraph with 4 edges is rs,rt,st,sv4. Obviously, N2G1=3, N3G1=4, and N4G1=1. Similarly, we can calculate NiGj, 2≤i,j≤4, which are N2G2=1, N3G2=3, and N4G2=1; N2G3=1, N3G3=4, and N4G3=1; and N2G4=0, N3G4=3, and N4G4=1. Figure 2 shows a visualization of reliability polynomials for all graphs in G4,4. Clearly, for all 0<p<1, R3G1;p>R3G3;p>R3G2;p>R3G4;p, so G1 is the uniformly most reliable graph in G4,4.Figure 1
All simple three-terminal graphs inG4,4 with three target vertices r,s,andt.
(a)(b)(c)(d)Figure 2
A visualization of reliability polynomials for graphs inG4,4.Example 2.
Figure3 shows two special simple three-terminal graphs in G8,26 with three target vertices r,s,andt. Each edge of these graphs survives independently with probability p. By calculation, we give a plot of R3H1;p−R3H2;p as shown in Figure 4. Clearly, R3H1;p>R3H2;p for p close to 1, and R3H1;p<R3H2;p for p close to 0. This article later proves that H1 is the locally most reliable graph for p close to 1 and H2 is the locally most reliable graph for p close to 0 in G8,26.
Many studies focus on determining a uniformly most reliable graph for given number of verticesn and edges m, as shown in [1, 2, 14]. If there is no uniformly most reliable graph, researchers usually focus on determining the locally most reliable graph for p close to 0 or 1, as shown in [3, 17]. At present, there are few studies on determining whether there is a uniformly most reliable three-terminal graph. Therefore, in this paper, we study the uniformly most reliable graph and the locally most reliable graph of dense three-terminal graph. One can see that some dense graphs have uniformly most reliable three-terminal graphs as Example 1, and some does not have the uniformly most reliable graph but have locally most reliable three-terminal graphs as Example 2.Figure 3
Two special three-terminal graphs inG8,26 with three target vertices r,s,andt. The red dotted lines indicate the deleted edges.
(a)(b)Figure 4
A plot ofR3H1;p−R3H2;p.


## 3. Some Locally Most Reliable Three-Terminal Graphs

In this section, the locally most reliable three-terminal graph withn≥7 and m∈n2−n−4,n2−2 for p close to 0 is determined and the locally most reliable three-terminal graph with n≥7 and m∈n2−⌊n−3/2⌋,n2−2 for p close to 1 is also determined. Then, it is shown that for n≥7 and m∈n2−⌊n−3/2⌋,n2−2, there is no uniformly most reliable graph in Gn,m. For n=4,5,6 and m=n2−2, there is a uniformly most reliable three-terminal graph. To prove these results, we first introduce some related lemmas.Lemma 1.
(see [17]). Let n≥1 and 0≤m≤n−1 be positive integers. If m≠3, then the unique simple graph on n vertices and m edges with the maximum number of P3 is Sm+1∪Kn−m−1¯. If m=3, then there are two simple graphs with the maximum number of P3: K3∪Kn−3¯ and S4∪Kn−4¯.In general, it is difficult to calculate the three-terminal reliability polynomial of graph. Therefore, we study the locally most reliable graph by the following Lemma2, which is extracted from [14].Lemma 2.
Let the three-terminal reliable polynomials ofG,H∈Gn,m be R3G;p=∑i=2mNiGpi1−pm−i and R3H;p=∑i=2mNiHpi1−pm−i.LetNiG=NiH for 1≤i<k and for l<i≤m, where k and l are integers. Then,(1)
forp close to 0, if NkG>NkH, then R3G;p>R3H;p;(2)
forp close to 1, if NlG>NlH, then R3G;p>R3H;p.By Lemma2, we get the following conclusions:(1)
IfG∈Gn,m is the locally most reliable graph for p close to 0, then it must contain the triangle rst and the value of N3G is the maximum among graphs containing the triangle rst in Gn,m.(2)
Anrst-cutset of G is a set of edges whose deletion results in the disconnection of vertices r,s, and t in G and the number of edges is its size. The edge connectivity of r,s, and t in G is the smallest size of an rst-cutset of G, denoted by λrstG or simply λG. If G∈Gn,m is the locally most reliable graph for p close to 1, then it must have the maximum λrstG. Since Ni=mi (m−λ+1≤i≤m) and Nm−λ=mλ−a, where a is the number of the rst-cutsets with size λ, G must have the minimum a among the graphs with the largest edge connectivity of r,s, and t in Gn,m.Now, we demonstrate the locally most reliable graph for three-terminal graphs forp close to 0 or 1. We first introduce two important graphs for this section, as follows:Letn≥7 and 2≤l≤n−4 be positive integers. Using An,l denotes the three-terminal graph on n vertices and n2−l edges with vertex set VAn,l=r=v1,s=v2,t=v3,v4,…,vn and edge set EAn,l=vivj|1≤i<j≤n−v4vi+3|2≤i≤l+1.Letn≥7 and 2≤l≤n−3/2 be positive integers. Using An,l′ denotes the three-terminal graph on n vertices and n2−l edges with vertex set VAn,l′=r=v1,s=v2,t=v3,v4,…,vn and edge set EAn,l′=vivj|1≤i<j≤n−v2iv2i+1|2≤i≤l+1.Figure5 depicts these two three-terminal graphs with 11 vertices and 51 edges.Figure 5
GraphA11,4 (a) and Graph A11,4′ (b). The red dotted lines indicate the deleted edges.
(a)(b)Theorem 1.
Letn≥7, 2≤l≤n−4 and m=n2−l be positive integers. Then,(1)
ifl=3, then the graph An,3∗=An,3∪v4v7−v5v6 is the unique locally most reliable graph in Gn,m for p close to 0;(2)
ifl≠3, then the graph An,l is the unique locally most reliable graph in Gn,m for p close to 0.Proof.
Suppose thatG is the locally most reliable graph in Gn,m for p close to 0. Then, by Lemma 2, G must contain the triangle rst and N3 (the number of rst-subgraphs with 3 edges in G) must be maximum among graphs containing the triangle rst in Gn,m.
For the sake of calculatingN3, using a,b,andc denotes the number of rst-subgraphs with 3 edges containing 2,1,0 edges in triangle rst, respectively. Then, a is the number of sets rs,st,vivj, rs,rt,vivj, and rt,st,vivj (1≤i,j≤n), b is the number of sets rs,rvi,tvi, rs,svi,tvi, rt,rvi,svi, rt,tvi,svi, st,rvi,svi, and st,rvi,tvi (4≤i≤n), and c is the number of set vir,vis,vit (4≤i≤n). It is no hard to see that N3=a+b+c. Clearly, for graphs containing the triangle rst in Gn,m, a is a constant which equals 3m−3+1, and N3 takes the maximum value if and only if b and c attains the maximum value. Note that if c takes the maximum value n−3, then the value of b also reaches its maximum; that is, EG contains the edges vir,vis,vit for all 4≤i≤n. Now, consider the remaining n2−l−3n+6 edges among nontarget vertices in G that has not been described. Since G is a dense graph, it is often easier to consider the deleted l edges among nontarget vertices.
By Lemma2, we continue to calculate the coefficients Ni=bi+ci (i>3), where bi and ci are the number of minimal rst-subgraphs and nonminimal rst-subgraphs with i edges, respectively. We now compute N4. Clearly, b4 is the sum of the numbers of sets svi,vit,svj,vjr, svi,vivj,vjt,sr, and svi,vivj,vjt,vjr (4≤i,j≤n). The nonminimal rst-subgraph with 4 edges includes two cases: one is containing the minimal rst-subgraph with 2 edges and the other is containing the minimal rst-subgraph with 3 edges but no minimal rst-subgraph with 2 edges. By calculation, b4=6n−32+12m−3n+6+6m−3n+6 and c4=3m−32+m−3+n−3m−3+6n−3m−6 which are constants. So, N4 is a constant.
Furthermore, we need to calculateN5. Clearly, b5 is the sum of the numbers of sets svi,vivj,vjr,rvk,vkt, svi,vivj,vjvk,vkt,rt, svi,vivj,vjr,vjvk,vkt, and rvi,svi,vivj,vjvk,vkt (4≤i,j,k≤n). The nonminimal rst-subgraph with 5 edges includes three cases: containing the minimal rst-subgraph with 2 edges, containing the minimal rst-subgraph with 3 edges but no minimal rst-subgraph with 2 edges, and containing the minimal rst-subgraph with 4 edges but no minimal rst-subgraph with less than 4 edges. By calculation, c5=3m−33+m−32+7n−3m−62+3n−3m−6−12n−32+18m−3n+6m−10+6m−3n+6+6m−9n−32, which is a constant. And(2)b5=12m−3n+6n−5+24∑i=4ndvi−32=12∑i=4ndvi−32+12m−3n+6n−7=24∑i=4ndi2+24l+12n−3n−42−48n−4l+12m−3n+6n−7,where dvi is the degree of vi in G, and di is the number of edges deleted on the nontarget vertex vi4≤i≤n, which is the degree of vi in G¯. Note that the number of subgraphs as P3 in G¯ is ∑i=4ndi2. Obviously, N5 of R3G;p is related to βG¯P3, the number of subgraphs as P3 in G¯. There are at least three isolate vertices in G¯, which are target vertices in G. βG¯P3 is corresponding with n−3 nontarget vertices.(1)
By Lemma1, if l=3, then the number of P3 in a simple graph with n−3 vertices and l edges reaches the maximum if the graph is either K3∪Kn−6¯ or S4∪Kn−7¯. Thus, G¯ is either K3∪Kn−6¯∪r,s,t or S4∪Kn−7¯∪r,s,t, which means that G is either An,3 or An,3∗, where N5An,3=N5An,3∗. So, we need to compare N6An,3 and N6An,3∗, which can be calculated as the same analysis of N5. For convenient, if H∈Gn,m, then let H^ be the graph H−s,t. Then, N6An,3=m−33+3m−34+3n−3m−62+7n−3m−63+6m−92−12m−9−13n−32−30n−33+18m−102+6m−10−36n−5+12n−5m−13+12m−3n+7m−3n+6+12n+24m−459βAn,3^P3−66βAn,3^K3+30βAn,3^P4+6βAn,3^S4 and N6An,3∗=m−33+3m−34+3n−3m−62+7n−3m−63+6m−92−12m−9−13n−32−30n−33+18m−102+6m−10−36n−5+12n−5m−13+12m−3n+7m−3n+6+12n+24m−459βAn,3∗^P3−66βAn,3∗^K3+30βAn,3∗^P4+6βAn,3∗^S4. By calculation, βAn,3^P4=βAn,3∗^P4, βAn,3^S4−βAn,3∗^S4=−1 and βAn,3^K3−βAn,3∗^K3=1. So,(3)N6An,3−N6An,3∗=30βAn,3^P4−βAn,3∗^P4+6βAn,3^S4−βAn,3∗^S4−66βAn,3^K3−βAn,3∗^K3=−72<0.Therefore, ifl=3, the graph An,3∗ is the unique locally most reliable graph in Gn,m for p close to 0.(2)
By Lemma1, if l≠3, then the number of P3 in a simple graph with n−3 vertices and l edges is maximized only if the graph is Sl+1∪Kn−4−l¯. Thus, G¯ is Sl+1∪Kn−4−l¯∪r,s,t, which means that G is An,l. Therefore, if l≠3, then the graph An,l is the unique locally most reliable graph in Gn,m for p close to 0.Theorem 2.
Letn≥7, 2≤l≤⌊n−3/2⌋, and m=n2−l be positive integers. Then, An,l′ is the unique locally most reliable graph in Gn,m for p close to 1.Proof.
LetG∈Gn,m be the most reliable graph for p close to 1. By Lemma 2, G must have the largest edge connectivity of r,s, and t, which is the size of the smallest rst-cutset of G as large as possible. For convenient, let ℋn,m be the set of three-terminal graph with the largest edge connectivity of r,s, and t. Obviously, G∈ℋn,m.
For any graphH∈ℋn,m, let C be the minimal rst-cutset of H, then there must exist a component containing just one target vertex and k0≤k≤n−3 nontarget vertices ui1≤i≤k in H−C, without loss of generality, setting this target vertex as r. Clearly, λH≤mindr,ds,dt≤n−1. If dr=ds=dt=n−1, then C≥dr−k+2k=dr+k≥n−1. Hence, λ can arrive at the maximum value n−1 if and only if dr=ds=dt=n−1. Thus, three target vertices in H are adjacent to every vertex in VH. However, the connections among nontarget vertices are various. In order to get the precise construction of G, by Lemma 2, we need to consider the coefficient Nm−ii≥λ. Obviously, Nm−i=mm−i−mi, where mi is the number of the rst-cutsets of size i. For given i, mm−i is a constant and Nm−i is corresponding with mi. Let δ be the minimum degree of H. Since n≥7 and n2−⌊n−3/2⌋≤m≤n2−2, we have δ≥n−1−⌊n−3/2⌋≥4.
Continue to calculate the minimalrst-cutset of H, C=λ+∑i=1kdui−2k−2m′≥λ+δk−2k−2k2=λ−k2+δ−1k, where m′ is the edge number among nontarget vertices u1,u2,…,uk. If k>δ−2, then C≥dr+k>λ+δ−2. If 1≤k≤δ−2, then C≥λ+δ−2, where the equation holds if the components containing r in H−C are following two cases: one is composed of target vertex r and one nontarget vertex with degree δ; the other is composed of target vertex r and δ−2 nontarget vertices with degree δ and the induced subgraph by vertices in this component is Kδ−1. So, the number of C with size λ+1,λ+2,…,λ+δ−3 is 0. Meanwhile, the number of C with size λ is 3. By calculation, we see that mjH=3m−λj−λ for λ≤j≤λ+δ−3 and mλ+δ−2H=3m−λδ−2+3n1+3n2, where n1 is the number of nontarget vertices with degree δ and n2 is the number of Kδ−2 in the induced subgraph of nontarget vertices with degree δ.
Similarly, as the calculation ofH, we have mjG=3m−λj−λ for λ≤j≤λ+δG−3 and mλ+δG−2G=3m−λδG−2+3n1′+3n2′, where n1′ is the number of nontarget vertices with degree δG and n2′ is the number of KδG−2 in the induced subgraph of nontarget vertices with degree δ in G. Obviously, n1′>0, n2′≥0 and if δG<δ, then mjG=mjH for λ≤j≤λ+δG−3, and mλ+δG−2G>3m−λδG−2 but mλ+δG−2H=3m−λδG−2. So, Nm−jG=Nm−jH for λ≤j≤λ+δG−3 and Nm−λ+δG−2G<Nm−λ+δG−2H, which contradicts the assumption that G is the most reliable graph for p close to 1. Then, we have δG≥δ.
Clearly,δG=⌊2m−3n+6/n−3⌋+3. Since n2−⌊n−3/2⌋≤m≤n2−2, the minimum degree of graph G is larger than n−2, which implies that for each v∈VG, dv≥n−2.
Therefore,An,l′ is the unique locally most reliable graph in Gn,m for p close to 1.
As a straightforward consequence of Theorems1 and 2, we obtain the following theorem.Theorem 3.
Letn≥7 and 2≤l≤⌊n−3/2⌋ be positive integers. If m=n2−l, then there is no uniformly most reliable three-terminal graph in Gn,m.Three specific classes of graphs with ordern and size m=n2−2 are uniformly most reliable graphs.Remark 1.
Forn = 4 and m = 4, there is a uniformly most reliable three-terminal graph in G4,4 (see Example 1). For n = 5 and m = 8, there is a uniformly most reliable three-terminal graph is G1 in G5,8 (graphs are shown in Figure 6, and the comparison of the reliability polynomial is shown in Table 1). For n = 6 and m = 13, there is a uniformly most reliable three-terminal graph is G1 in G6,13 (graphs are shown in Figure 7, and the comparison of the reliability polynomial is shown in Table 2).Figure 6
All simple three-terminal graphs inG5,8 with three target vertices r,s,andt.
(a)(b)(c)(d)(e)(f)(g)(h)Table 1
Reliability polynomials of graphs forR3G;p.
R3G;pN2N3N4N5N6N7N8R3G1;p32560552881R3G2;p32357542881R3G3;p32051502781R3G4;p32056542881R3G5;p11655542881R3G6;p11351532881R3G7;p11246492781R3G8;p0642482781Figure 7
All simple three-terminal graphs inG6,13 with three target vertices r,s,andt.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)Table 2
Reliability polynomials of graphs forR3G;p.
R3G;pN2N3N4N5N6N7N8N9N10N11N12N13R3G1;p352337101716051689128471528678131R3G2;p34730495515501661127671428678131R3G3;p34729795315521662127671428678131R3G4;p34528390715011634126871328678131R3G5;p34226488914941633126871328678131R3G6;p34225984914281577124070528578131R3G7;p12622786314861632126871328678131R3G8;p12319980514321604126071228678131R3G9;p12218876113651548123270428578131R3G10;p0913268713081520122470328578131


## 4. The Uniformly Most Reliable Three-Terminal Graph

For the three-terminal graph withn2 edges, it is complete graph, which is also the uniformly most reliable graph. In this section, we determine the uniformly most reliable graph in Gn,m with m=n2−1.When we remove one edge fromKn with three target vertices, there are only three cases: the edge between target vertices; the edge between a target vertex and a nontarget vertex; and the edge between nontarget vertices. Let n≥5 and m=n2−1 be positive integers.(1)
UsingXn denotes the three-terminal graph on n vertices and m edges with vertex set VXn=r=x1,s=x2,t=x3,x4,…,xn and edge set EXn=xixj|1≤i<j≤n−rs.(2)
UsingYn denotes the three-terminal graph on n vertices and m edges with vertex set VYn=r=y1,s=y2,t=y3,y4,…,yn and edge set EYn=yiyj|1≤i<j≤n−ry4.(3)
UsingZn denotes the three-terminal graph on n vertices and m edges with vertex set VZn=r=z1,s=z2,t=z3,z4,…,zn and edge set EZn=zizj|1≤i<j≤n−z4z5.Theorem 4.
Letn≥5 and m=n2−1 be positive integers. Then, Zn is the unique uniformly most reliable graph in Gn,m.Proof.
By the definition of three-terminal reliability polynomial, if we can prove that there are morerst-subgraphs with i edges in Zn than in Xn and Yn for each 2≤i≤n2−1, then Zn is the unique uniformly most reliable graph in Gn,m.
We complete this proof by constructing two injective mapsfX and fY, from the rst-subgraphs with i edges in Xn and Yn to the rst-subgraphs with i edges in Zn, respectively.
Construct the mapfX:
LetS be an rst-subgraph with i edges in Xn, where 2≤i≤n2−1. According to whether x4x5∈S, there are two cases we need to consider.Case 1: ifS does not contain the edge x4x5, then fXS=zizj|xixj∈S. The image is an rst-subgraph of Zn with the same number of edges as S. And this image does not contain the edge rs.Case 2: assume thatS contains the edge x4x5.Case 2.1: ifS−x4x5 is still an rst-subgraph, then fXS=zizj|xixj∈S∪rs−z4z5. The image is an rst-subgraph of Zn with the same number of edges as S. Since this image contains the edge rs, it is distinct from Case 1. And fXS−rs is still an rst-subgraph.Case 2.2: ifS−x4x5 is not an rst-subgraph, but an rt-subgraph or an st-subgraph, then fXS=zizj|xixj∈S∪rs−z4z5. The image is an rst-subgraph of Zn with the same number of edges as S. Since the image contains rs and fXS−rs is not an rst-subgraph, it is distinct from the above cases. It is clear to see that in Case 2.2, fXS contains either the edge st and an edge rzi for some 4≤i≤n, or the edge rt and an edge szj for some 4≤j≤n, or an edge rzi and an edge szj for some 4≤i,j≤n.Case 2.3: assume thatS−x4x5 is not an rst-subgraph, or rt-subgraph, or st-subgraph. In this case, all rst-subgraphs, rt-subgraphs, and st-subgraphs in S contain the edge x4x5. Thus, the image of the map defined by the above cases is not an rst-subgraph of Zn. Let S′ be a minimal rst-subgraph in S. In S′−x4x5, there are two components containing x4 and x5, respectively. Targets r and s are in the same component; otherwise, S−x4x5 is either an rt-subgraph or an st-subgraph. Without loss of generality, let r,s be in the component containing x4 in S′−x4x5 and let t be in the same component as x5 in S′−x4x5.Case 2.3.1: ifS′ is consisted of an edge sxj, a minimal x4xj-subgraph, the edge rx4, the edge x4x5, and a minimal x5t-subgraph, then fXS=zizj|xixj∈S∪z5zj|sxj∈S∪rs−z4z5. S does not have both edges x5xj and sxj; otherwise, an edge x5xj, an edge sxj, and a x5t-subgraph will get a st-subgraph that does not contain the edge x4x5 which contradicts the condition of Case 2.3. Therefore, fXS has the same number of edges as S. In fXS, we have an rst-subgraph of Zn which is consisted of an edge z5zj, a z4zj-subgraph, the edge rz4, a z5t-subgraph, and the edge rs. Since fXS contains the edge rs but does not contain any edge szj3≤j≤n and fXS−rs is not an rst-subgraph, fXS is distinct from the above cases. The image fXS in this case contains the edge rz4.Case 2.3.2: ifS′ is consisted of an edge rxj, a minimal sx4xj-subgraph, the edge x4x5, and a minimal x5t-subgraph, then fXS=zizj|xixj∈S∪z5zj|rxj∈S∪rs−z4z5. Similarly, as Case 2.3.1, S does not have both edges x5xj and rxj. Therefore, fXS has the same number of edges as S. In fXS, we have an rst-subgraph of Zn which is consisted of an edge z5zj, a sz4zj-subgraph, a z5t-subgraph, and the edge rs. Since fXS contains edges rs and szj for some 4≤j≤n but does not contain any edge rzi3≤i≤n and fXS−rs is not an rst-subgraph, fXS is distinct from the above cases.Case 2.3.3: ifS′ is consisted of the edge rx4, the edge sx4, the edge x4x5 and a minimal x5t-subgraph, then fXS=zizj|xixj∈S∪rz5|sx4∈S∪z5zj|sxj∈S,j≠4∪rs−z4z5. Similarly, as Case 2.3.1, S does not have both edges x5xj and sxj. Therefore, fXS has the same number of edges as S. In fXS, we have an rst-subgraph of Zn is consisted of the edge rz4, the edge rz5, a z5t-subgraph, and the edge rs. Since fXS contains edges rs, rz4, and rz5 but does not contain any edge szj3≤i≤n and fXS−rs is not an rst-subgraph, fXS is distinct from the above cases.
Since the mapfX defined on each of these cases yields rst-subgraph of Zn as disjoint images, the map is injective.
Because there are at least as manyrst-subgraphs with i edges in Zn as in Xn for 2≤i≤n2−1, Zn is more reliable than Xn for all p0≤p≤1.
Construct the mapfY:
LetS be an rst-subgraph with i edges in Yn, where 2≤i≤n2−1. According to whether y4y5∈S, there are two cases we need to consider.Case 1: ifS does not contain the edge y4y5, then fYS=zizj|yiyj∈S. The image is an rst-subgraph of Zn with the same number of edges as S. And this image does not contain the edge rz4.Case 2: assume thatS contains the edge y4y5.Case 2.1: ifS−y4y5 is still an rst-subgraph, then fYS=zizj|yiyj∈S∪rz4−z4z5. The image is an rst-subgraph of Zn with the same number of edges as S. Since the image contains the edge rz4, it is distinct from Case 1. And fYS−rz4 is still an rst-subgraph.Case 2.2: ifS−y4y5 is not an rst-subgraph but is an rsy5-subgraph and a y4t-subgraph, or an ry5-subgraph and an sty4-subgraph, or an rty5-subgraph and an sy4-subgraph, then fYS=zizj|yiyj∈S∪rz4−z4z5. The image is an rst-subgraph of Zn with the same number of edges as S. Since the image contains rz4 and fYS−rz4 is not an rst-subgraph, it is distinct from the above cases. Since S contains an edge ryj for some 2≤j≤n and j≠4, the image also contains an edge rzj for some 2≤j≤n and j≠4.Case 2.3: assume thatS−y4y5 does not contain an rst-subgraph, or an rsy5-subgraph and a y4t-subgraph, or an ry5-subgraph and an sty4-subgraph, or an rty5-subgraph and an sy4-subgraph. In this case, all rst-subgraphs contain the edge y4y5. And S−y4y5 is either an rsy4-subgraph and a y5t-subgraph, or an rty4-subgraph and an sy5-subgraph, or an ry4-subgraph and an sty5-subgraph. Therefore, the image of the map defined for the above cases is not an rst-subgraph of Zn. Let S′ be a minimal rst-subgraph in S.Case 2.3.1: ifS′ is consisted of an edge ryj, a minimal sy4yj-subgraph, the edge y4y5, and a minimal y5t-subgraph, then fYS=zizj|yiyj∈S∪z5zj|ryj∈S∪rz4−z4z5. If S contains both edges y5yj and ryj, then the edge y5yj, the edge ryj, an sy4yj-subgraph, and a y5t-subgraph will yield an rst-subgraph without the edge y4y5, which contradicts the condition of Case 2.3. Consequently, S does not have both edges y5yj and ryj and fYS has the same number of edges as S. In fYS, we have an rst-subgraph of Zn which is consisted of an edge z5zj, an sz4zj-subgraph, a z5t-subgraph, and the edge rz4. Since fYS contains the edge rz4 but does not contain any edge rzj2≤j≤n,j≠4 and fYS−rz4 is not an rst-subgraph, fYS is distinct from the above cases. In this case, each rs-subgraph in image fYS does not contain z5.Case 2.3.2: ifS′ is consisted of an edge ryj, a minimal ty4yj-subgraph, the edge y4y5, and a minimal sy5-subgraph, then fYS=zizj|yiyj∈S∪z5zj|ryj∈S∪rz4−z4z5. Similarly, as Case 2.3.1, S does not have both edges y5yj and tyj. Therefore, fYS has the same number of edges as S. In fYS, we have an rst-subgraph of Zn which is consisted of an edge z5zj, a tz4zj-subgraph, a sz5-subgraph, and the edge rz4. Since fYS contains the edge rz4 but does not contain any edge rzj2≤j≤n,j≠4 and fYS−rz4 is not an rst-subgraph and all rs-subgraph in fYS contain z5, fYS is distinct from the above cases. In fYS, each rt-subgraph does not contain z5.Case 2.3.3: ifS′ is consisted of an edge ryj, a minimal y4yj-subgraph, the edge y4y5, and a minimal sty5-subgraph, then fYS=zizj|yiyj∈S∪z5zj|ryj∈S∪rz4−z4z5. Similarly, as Case 2.3.1, S does not have both edges y5yj and ryj. Therefore, fYS has the same number of edges as S. In fYS, we have an rst-subgraph of Zn which is consisted of an edge z5zj, a z4zj-subgraph, a stz5-subgraph, and the edge rz4. Since fYS contains the edge rz4 but does not contain any edge rzj2≤j≤n,j≠4 and fYS−rz4 is not an rst-subgraph and all rs-subgraphs and rt-subgraphs in fYS contain z5, fYS is distinct from the above cases.
Since the mapfY defined on each of these cases yields rst-subgraph of Zn as disjoint images, the map is injective.
Because there are at least as manyrst-subgraphs with i edges in Zn as in Yn for 2≤i≤n2−1, Zn is more reliable than Yn for all p0≤p≤1.
From the above argument, we conclude thatZn is the unique most reliable graph in Gn,m for all p0≤p≤1.


## 5. Conclusion

The reliability of three-terminal graphs with large number of edges are investigated in this article, which fills in the blank of this research.When the number of verticesn is 4,5, or 6 and the number of edges m is n2−2, the uniformly most reliable graph is determined with comparisons in Example 1 and Remark 1. When n≥7 and n2−⌊n−3/2⌋≤m≤n2−2, there is no uniformly most reliable graph. However, the locally most reliable graph in Gn,m for p close to 0 or 1 is justified by Theorems 1 and 2, respectively. It is worth considering whether there is a uniformly most reliable graph in the class of three-terminal graphs by deleting more edges from Kn with three target vertices.The uniformly most reliable graph inGn,n2−1 is determined, which is a graph by removing an edge between nontarget vertices from Kn with three target vertices. This conclusion is significant in comparison with the conclusion given by Betrand et al. [14], which states that the uniformly most reliable graph with n2−1 edges for two-terminal graphs is a graph by deleting an edge between nontarget vertices from Kn with two target vertices. For m=n2−1, we conjecture that the uniformly most reliable graph for k-terminal graphs is a graph by removing an edge between nontarget vertices from Kn with k target vertices.Based on these results, we found that whenm≥n2−⌊n−3/2⌋, there are no uniformly most reliable three-terminal graphs in most three-terminal graph classes, and then it is interesting to study the uniformly most reliable three-terminal graphs for sparse graphs or other general graphs. In addition, it is significant to extend the results of this paper and [14] to k-terminal graphs.



---

*Source: 6664959-2021-04-20.xml*