Frequency-hopping scheduling algorithm for energy-efficient IoT, long-range, wide-area networks

1.   Introduction

Network reliability is an important topic in network research, network performance analysis, and combinatorial mathematics. And researchers usually use graph theoretic models to study it extensively. The network reliability can be separated into three types of models: edges are perfectly reliable while vertices survive independently with a fixed probability ^[9,12]; vertices are perfectly reliable while edges survive independently with a fixed probability ^[3,11,16]; and vertices and edges survive independently of each other with some fixed probabilities ^[6,8]. There are two aspects on the network reliability: reliability analysis and reliability design. The purpose of reliability analysis is to compute the reliability or unreliability polynomial of a given graph ^[7,19,23,24]. The purpose of reliability design is to find the graphs with the maximum reliability polynomial or the minimum unreliability polynomial among graphs with the same number of vertices and edges ^{[1,2,3,8,10,11,14,16]}. In addition, according to the number of vertices which are connected in the graph, these models can be divided into two main research categories: $k$-terminal reliability (the probability that $k$ specified target vertices in a given graph are connected) ^{[2,7,13,15,17,23,24]}; and all-terminal reliability (the probability that the entire graph is connected) ^{[1,3,8,9,10,11,14,16,19,21,22]}.

In practice, the network is required to run normally even if some edges are fail. If each edge of the network survives independently with a fixed probability, the network with the largest connected probability of target vertices is defined as the most reliable graph. There are more results about the most reliable graphs for all-terminal graphs, seeing ^{[1,3,10,14,21]}. However, there are a few studies on reliability analysis of $k$-terminal networks, which calculate the reliability polynomials of graphs ^[7,23,24]. And there are even fewer results on the reliability design of $k$-terminal networks. In 2018, Betrand et al. ^[2] gave some important results about the most reliable two-terminal graph, and determined several locally most reliable two-terminal graphs when the vertices are perfectly reliable and the edges survive independently with probability $0\leq p\leq1$. And they also proved that there is no uniformly most reliable two-terminal simple graph in some graph families. It is natural to consider the following problems.

Problem. Do the three-terminal graphs have locally most reliable graph or uniformly most reliable graph as two-terminal graphs? How does one construct locally most reliable three-terminal graphs with given number of vertices and edges? Is the locally most reliable three-terminal graph also uniformly most reliable?

With these questions, this research extends the study from the two-terminal graphs to three-terminal graphs, studies the locally most reliable three-terminal simple sparse graphs (graphs with edges less than or equal to a constant multiple of the number of vertices) and considers whether the locally most reliable graph is also the uniformly most reliable graph. The structure of this paper is organized as follows. Fundamental definitions and notations are given in Section $2$. In Section $3$, some locally most reliable graphs are determined for three-terminal graphs with $n$ vertices and $m$ edges, where $n\geq5$ and $9 < m\leq4n-10$. Some locally most reliable graphs are further evaluated that they are not uniformly most reliable graphs, when $11 < m\leq3n-5$ and $m\equiv 2(\bmod 3)$ or $3n-5 < m\leq4n-10$. Section $4$ summarizes the results of this research.

2.   Basic concepts and notations

Some basic notation is list here. For integers $a, b$ and $r$, the notation $a\equiv r(\bmod b)$ indicates that the reminder of $a$ divided by $b$ is $r$, and $\lfloor\frac{a}{b}\rfloor$ is the largest integer not greater than $\frac{a}{b}$. In this paper, we will only consider simple graphs in which there are no multiple edges and loops. In a graph $G$, the degree of the vertex $v$ is the number of edges incident with $v$, denoted by $d(v)$. The complete graph on $n$ vertices is denoted by $K_n$, and $K_{1, n}$ denotes the simple graph on $n+1$ vertices with one vertex of degree $n$ and $n$ vertices of degree 1. The union of graphs $G$ and $H$ is the graph with vertex set $V(G)\cup V(H)$ and edge set $E(G)\cup E(H)$, which is denoted by $G\cup H$. If $l$ is a positive integer, then $l\cdot G$ denotes the disjoint union of $l$ copies $G$. The join of $G$ and $H$, which is denoted by $G\vee H$, has vertex set $V(G)\cup V(H)$ and edge set $E(G)\cup E(H)\cup \{uv|u\in G, v\in H\}$. Suppose $u$ and $v$ are two vertices in $G$, $G\cup \{uv\}$ is the graph obtained by adding an edge between $u$ and $v$ to $G$, and $G-\{uv\}$ is the graph obtained by deleting the edge between $u$ and $v$ from graph $G$. For notation and terminology not defined in this paper we follow ^[4].

A three-terminal graph is an undirected and simple graph $G = (V(G), E(G))$ with three specified target vertices $r, s$ and $t$ in $V(G)$. Using $\mathcal{G}_{n, m}$ denotes the set of all three-terminal graphs on $n$ vertices and $m$ edges. The probability that three specified target vertices $r, s, t$ of a graph $G\in\mathcal{G}_{n, m}$ remain connected when each of its edges survives independently with probability $p$ is called the three-terminal reliability (or the three-terminal reliability polynomial) of $G$. The $rst$-subgraph of $G$ is the subgraph of $G$ such that $r, s, t$ are connected with each other. Let $N_i(G)$ (simply $N_i$) be the number of $rst$-subgraphs with $i$ edges of graph $G$, then the three-terminal reliability polynomial of the graph $G\in\mathcal{G}_{n, m}$ can be defined as

For some three-terminal graphs with small number of vertices and edges, we can compute the reliability polynomial directly by definition. However, for a three-terminal graph with many vertices and edges, the number of $rst$-subgraphs with $i$ edges is very large, which possibly leads to the loss or repetition of some $rst$-subgraphs in the process of finding $rst$-subgraphs. So, it is very difficult to determine the coefficients of the reliability polynomial by the definition. In order to obtain the reliability polynomial, it is necessary to use the Factorization approach as indicated in the following lemma.

Lemma 2.1. (^[18]) For any edge $e$ in a three-terminal graph $G\in\mathcal{G}_{n, m}$, the following factorization holds:

where $G\cdot e$ is the graph obtained by contracting the endpoints of edge $e$ in $G$ and $G-e$ is the graph obtained by deleting the edge $e$ from $G$.

Example 1. Figure 1 depicts two special three-terminal graphs in $\mathcal{G}_{7, 14}$ with three target vertices $r, s, t$. Each edge of these graphs survives independently with probability $p$. By definition, we have

$R_3(G_1;p) = \sum\limits_{i = 2}^{14}N_i(G_1)p^i(1-p)^{14-i}$, $R_3(G_2;p)$ = $\sum\limits_{i = 2}^{14}N_i(G_2)p^i(1-p)^{14-i}.$

By calculation, we get

$R_3(G_1;p)-R_3(G_2;p)$ = $52p^{14}-490p^{13}+2039p^{12}-4898p^{11}$ + $7433p^{10}-7288p^9+4463p^8-1464p^7$ + $63p^6+122p^5-34p^4+2p^3.$

Figure 2 gives a plot of $R_3(G_1;p)-R_3(G_2;p)$. Clearly, $G_1$ is more reliable than $G_2$ for $p\rightarrow0$ (the value of $p$ sufficiently close to 0) and for $p\rightarrow1$ (the value of $p$ sufficiently close to 1). In fact, by Theorems 3.3 and 3.4, it is easy to see that when $n = 7$ and $m = 14$, $G_1\cong B_{7, 7}$ and $G_1$ is the locally most reliable graph in $\mathcal{G}_{7, 14}$ for $p\rightarrow0$ and for $p\rightarrow1$. However, when $p$ is in the range $(0.1, 0.65)$, $G_2$ is more reliable than $G_1$. Thus, there is no uniformly most reliable graph in $\mathcal{G}_{7, 14}$.

According to the definitions of the locally most reliable all-terminal graph ^[1] and the uniformly most reliable two-terminal graph ^[2], we defined the locally most reliable graph and the uniformly most reliable graph for three terminal graphs.

Definition 2.1. For $p_0 = 0$ $($or $1$$)$, if there is an $\varepsilon > 0$ such that $R_3(G; p)\geq R_3(H; p)$ for all $H\in\mathcal{G}_{n, m}$ and for all $p\in[0, 1]\cap(p_0-\varepsilon, p_0+\varepsilon)$, then $G$ is the locally most reliable graph in $\mathcal{G}_{n, m}$ for $p\rightarrow0$ $($or for $p\rightarrow1$$)$. In particular, a graph $G$ is the uniformly most reliable graph in $\mathcal{G}_{n, m}$, if $R_3(G; p)\geq R_3(H; p)$ for all $H\in\mathcal{G}_{n, m}$ and all $0\leq p\leq1$.

3.   Reliability of graphs with $9\leq m\leq4n-10$ edges

In this section, we determine some locally most reliable graphs in $\mathcal{G}_{n, m}$ for $9\leq m\leq4n-10$. Then we also consider whether these locally most reliable graphs are the uniformly most reliable graphs. An $rst$-subgraph with $i$ edges is minimal if it does not contain any $rst$-subgraphs with edges number less than $i$, otherwise it is non-minimal. An $rst$-cutset is a set of edges, whose removal makes at least two target vertices disconnected. And the $rst$-edge connectivity of $G$ is the smallest size of an $rst$-cutset, denoted by $\lambda(rst)$ or simply $\lambda$. It is difficult to find the exact cases that three target vertices are connected, which is NP-complete ^[20]. Therefore, we determine the most reliable graph by the following lemma.

Lemma 3.1.(^[1]) Let $G, H\in\mathcal{G}_{n, m}$, the three-terminal reliability polynomial of $G$ and $H$ is

$R_3(G; p) = \sum\limits_{i = 2}^mN_i(G)p^i(1-p)^{m-i}$ and $R_3(H; p) = \sum\limits_{i = 2}^mN_i(H)p^i(1-p)^{m-i},$ respectively.

Suppose there exist integers $k$ and $l$, such that $N_i(G) = N_i(H)$ for $2\leq i < k$ or for $l < i\leq m$. Then

$(1)$ If $N_k(G) > N_k(H)$, then $R_3(G; p) > R_3(H; p)$ for $p\rightarrow0$,

$(2)$ If $N_l(G) > N_l(H)$, then $R_3(G; p) > R_3(H; p)$ for $p\rightarrow1$.

From Lemma $3.1$, we see that if $G\in\mathcal{G}_{n, m}$ is the locally most reliable graph for $p\rightarrow0$, then it must contain the triangle $rst$ and $N_3$ is the largest among graphs containing the triangle $rst$ in $\mathcal{G}_{n, m}$. It is not hard to see that $N_i = \binom{m}{i}$ for $m-\lambda+1\leq i\leq m$ and $N_{m-\lambda} = \binom{m}{\lambda}-a$, where $a$ is the number of the $rst$-cutsets of size $\lambda$. Then for $p\rightarrow1$, if $G$ is the locally most reliable graph in $\mathcal{G}_{n, m}$, then it must have the largest $rst$-edge connectivity $\lambda$, the number of $rst$-cutsets of size $\lambda$ attains the minimum value.

We first introduce some important graphs which will be used below.

Let $n\geq4$ and $0\leq l\leq n-4$ be integers. The three-terminal graph with $n$ vertices, which is drawn as Figure 3, is denoted by $A_{n, l}$, where the vertex set $V(A_{n, l})$ is $\{r = v_1, s = v_2, t = v_3, v_4, \cdots, v_n\}$ and the edge set $E(A_{n, l})$ contains the following $3n-6+l$ edges:

Let $n\geq4$ and $4\leq w\leq n$ be integers. The three-terminal graph with $n$ vertices, which is drawn as Figure 4, is denoted by $B_{n, w}$, where the vertex set $V(B_{n, w})$ is $\{r = v_1$, $s = v_2$, $t = v_3$, $v_4$, $\cdots$, $v_w$, $\cdots$, $v_n\}$ and the edge set $E(B_{n, w})$ contains the following $3w-7$ edges:

Theorem 3.1. Let $n\geq5$ and $9\leq m\leq 3n-5$ be integers and $m\equiv 0$ or $1(\bmod 3)$. Then the graph

is the locally most reliable graph in $\mathcal{G}_{n, m}$ for $p\rightarrow0$.

Proof. Assume that $n$ and $m$ satisfy the given conditions and let $G$ be the locally most reliable graph in $\mathcal{G}_{n, m}$ for $p\rightarrow0$. By Lemma $3.1$, we see that $G$ must contain the triangle $rst$ and $N_3$ is the largest among graphs containing the triangle $rst$ in $\mathcal{G}_{n, m}$.

According to the $rst$-subgraph containing the edge number of triangle $rst$, the $rst$-subgraph with 3 edges are consisted of the following four cases:

Case 1. All of three edges are from the triangle $rst$, saying $rs, rt, st$.

Case 2. Two of three edges are from the triangle $rst$ and another edge not in the triangle, saying $rs, st, v_iv_j$, where $1\leq i\leq n, 4\leq j\neq i\leq n$.

Case 3. One of three edges is from the triangle $rst$ and other two edges are not in the triangle, saying $rv_i, v_is, rt$, where $4\leq i\leq n$.

Case 4. None of three edges is from the triangle $rst$, then they are $v_ir$, $v_is$, $v_it$, where $4\leq i\leq n$.

Note that the number of the $rst$-subgraphs in Cases 1 and 2 is $1$ and $3(m-3)$, respectively. $N_3$ attains the maximum value if and only if the number of the $rst$-subgraphs of both Case 3 and Case 4 attains maximum value. By calculation, if the number of the $rst$-subgraphs in Case 4 attains maximum value, then $E(G)$ must contain $\lfloor\frac{m-3}{3}\rfloor = \lfloor\frac{m}{3}\rfloor-1$ edge sets $\{v_ir, v_is, v_it\}$ ($4\leq i\leq \lfloor\frac{m}{3}\rfloor+2$). Since $m\equiv 0$ or $1(\bmod 3)$, the number of the $rst$-subgraphs in Case 3 attains the maximum value, while it is maximum in Case 4. Therefore we get the following.

If $m\equiv 0(\bmod 3)$, then $E(G) = \{rs, rt, st\}\cup\{v_iv_j|1\leq i\leq3, 4\leq j\leq \frac{m}{3}+2\}$, and $G$ is $A_{\frac{m}{3}+2, 0}$ $\cup$ $(n-\frac{m}{3}-2)\cdot K_1$.

If $m\equiv 1(\bmod 3)$, the edge set of $G$ is consisted of the triangle $rst$, $\frac{m-4}{3}$ edge subsets as $\{v_ir, v_is, v_it\}$ $(4\leq i\leq\frac{m+5}{3})$, and the remaining edge either joining one target vertex and one non-target vertex or connecting two non-target vertices. For convenience, the remaining edge is denoted by $e$. If $9\leq m\leq3n-11$, then the degrees of non-target vertices in $G-e$ are 3 or 0. There are four possible joining types for $e$. The first type is to connect two non-target vertices of degree 3, without losing generality setting $e = v_4v_5$, and the final graph is denoted by $G_1$. The second type is to join one non-target vertex of degree 3 and the other non-target vertex of degree 0, without losing generality setting $e = v_4v_\frac{m+8}{3}$, and the final graph is denoted by $G_2$. The third type is to connect two non-target vertices of degree 0, without losing generality setting $e = v_\frac{m+8}{3}v_\frac{m+11}{3}$, and the final graph is denoted by $G_3$. The fourth type is to join one target vertex and one non-target vertex of degree 0, without losing generality setting $e = rv_{(m+8)/3}$, and the final graph is denoted by $G_4$. By calculation, $N_4(G_1) > N_4(G_i)$ for $i\in\{2, 3, 4\}$. By Lemma $3.1$, $E(G) = E(G_1) = \{rs, rt, st, v_4v_5\}\cup\{v_iv_j|1\leq i\leq3, 4\leq j\leq \frac{m+5}{3}\}$, which implies that $G\cong A_{\frac{m+5}{3}, 1}\cup (n-\frac{m+5}{3})\cdot K_1$. If $3n-11 < m\leq3n-8$, then there are $n-4$ non-target vertices of degree 3 and only one non-target vertex of degree 0 in $G-e$. There are three possible types for $e$ and the final graph is in $\{G_1, G_2, G_4\}$. By calculation and comparison, we can see that $G\cong A_{\frac{m+5}{3}, 1}\cup (n-\frac{m+5}{3})\cdot K_1$. If $3n-8 < m\leq3n-5$, then the degrees of all non-target vertices in $G-e$ are equal to 3. Then $e$ is only one type to connect two non-target vertices of degree 3, which means that $G\cong{G_1}$. So, $G\cong A_{\frac{m+5}{3}, 1}\cup (n-\frac{m+5}{3})\cdot K_1$.

From the above argument, we see that $A_{\lfloor\frac{m}{3}\rfloor+2, m-3\lfloor\frac{m}{3}\rfloor}\cup (n-\lfloor\frac{m}{3}\rfloor-2)\cdot K_1$ is the locally most reliable graph in $\mathcal{G}_{n, m}$ for $p\rightarrow0$.

Theorem 3.2. Let $n\geq5$ and $9\leq m\leq 3n-5$ be integers and $m\equiv 0$ or $1(\bmod 3)$. Then the graph

is the locally most reliable graph in $\mathcal{G}_{n, m}$ for $p\rightarrow1$.

Proof. Let $A = A_{\lfloor\frac{m}{3}\rfloor+2, m-3\lfloor\frac{m}{3}\rfloor}\cup (n-\lfloor\frac{m}{3}\rfloor-2)\cdot K_1$. Let $G\in\mathcal{G}_{n, m}$ be the locally most reliable graph for $p\rightarrow1$. Then by Lemma $3.1$, $G$ must have the largest $rst$-edge connectivity $\lambda$, and the number of $rst$-cutsets of size $\lambda$ attains the minimum value among graphs with the largest $\lambda$.

Obviously, $\lambda \leq min\{d(r), d(s), d(t)\}\leq \lfloor\frac{m}{3}\rfloor+1$. If $\{rs, rt, st\}\cup\{v_iv_j|1\leq i\leq3, 4\leq j\leq\lfloor\frac{m}{3}\rfloor+2\}\subseteq E(G)$, then $min\{d(r), d(s), d(t)\} = \lfloor\frac{m}{3}\rfloor+1$. Let $C$ be the minimal $rst$-cutset of $G$, then there must exist a component containing just one target vertex and $k_1$ $(0\leq k_1\leq n-{3})$ non-target vertices $u_{i}(1 \leq i \leq k_1)$ in $G-C$, where $u_{1}, u_{2}, \cdots, u_{k} \in\left\{v_{i} \mid 4 \leq i \leq\left\lfloor\frac{m}{3}\right\rfloor+2\right\}$, and without loss of generality, setting this target vertex as $r$. Then the number of edges in $C$ is at least $\left\lfloor\frac{m}{3}\right\rfloor+1-k+2 k=\left\lfloor\frac{m}{3}\right\rfloor+1+k \geq\left\lfloor\frac{m}{3}\right\rfloor+1$. Thus $\lambda\geq \lfloor\frac{m}{3}\rfloor+1$. Hence, $\lambda$ can arrive at the maximum value $\lfloor\frac{m}{3}\rfloor+1$ if $\{rs, rt, st\}\cup\{v_iv_j|1\leq i\leq3, 4\leq j\leq\lfloor\frac{m}{3}\rfloor+2\}\subseteq E(G)$. Then $\lambda = \lfloor\frac{m}{3}\rfloor+1$.

If $m\equiv 0(\bmod 3)$, then $\lambda$ is $\frac{m}{3}+1$, $d(r) = d(s) = d(t) = \frac{m}{3}+1$, $r, s$ and $t$ are adjacent with each other. If there is a non-target vertex $v\in V(G)$ with $d(v)\neq0$ or $3$, then we have either $\lambda(G) < \frac{m}{3}+1$, or $N_{m-(\frac{m}{3}+1)}(G) < \binom{m}{\lambda}-3$. For each non-target vertex $v\in V(G)$, if $d(v) = 0$ or $3$, then $N_{m-\lambda}(G) = \binom{m}{\lambda}-3$. Since $G$ is the locally most reliable graph, by Lemma $3.1$, $N_{m-\lambda}$ must be maximum, then the degree of each non-target vertex is either $0$ or $3$. Thus, $G$ is $A$.

If $m\equiv 1(\bmod 3)$, then $\lambda$ is $\frac{m+2}{3}$, and $\{rs, rt, st\}\cap E(G)\geq2$. When $\{rs, rt, st\}\cap E(G) = 3$, similarly, we can find that there are four graphs with $\lambda = \frac{m+2}{3}$ and $N_{m-\lambda} = \binom{m}{\lambda}-3$, which are $A$, $A\cup \{rv_n\}-\{v_4v_5\}$, $A\cup \{v_4v_n\}-\{v_4v_5\}$, $A\cup \{v_{n-1}v_n\}-\{v_4v_5\}$, where the second and third graphs only occur when $m\leq 3n-8$ and the last only occurs when $m\leq 3n-11$. By calculation, the values of $N_{m-\lambda-1}$ of these four graphs is $\binom{m}{\lambda+1}-3m+12$, $\binom{m}{\lambda+1}-3m+6$, $\binom{m}{\lambda+1}-3m+6$ and $\binom{m}{\lambda+1}-3m+6$, respectively. Obviously, $\binom{m}{\lambda+1}-3m+12 > \binom{m}{\lambda+1}-3m+6$, by Lemma $3.1$, $G$ is $A$. When $\{rs, rt, st\}\cap E(G) = 2$, similarly, by calculation, we find that for all graphs with $\lambda = \frac{m+2}{3}$, there is $N_{m-\lambda} < \binom{m}{\lambda}-3$. Therefore, by Lemma 3.1, if $m\equiv 1(\bmod 3)$, then $\{rs, rt, st\}\cap E(G) = 3$ and $G$ is $A$.

Therefore, the graph $A_{\lfloor\frac{m}{3}\rfloor+2, m-3\lfloor\frac{m}{3}\rfloor}\cup (n-\lfloor\frac{m}{3}\rfloor-2)\cdot K_1$ is the locally most reliable graph in $\mathcal{G}_{n, m}$ for $p\rightarrow1$.

Theorems $3.1$ and $3.2$ show that when $n\geq5$, $9\leq m\leq 3n-5$ and $m\equiv 0$ or $1(\bmod 3)$, $A_{\lfloor\frac{m}{3}\rfloor+2, m-3\lfloor\frac{m}{3}\rfloor}$ $\cup(n-\lfloor\frac{m}{3}\rfloor-2)\cdot K_1$ is the locally most reliable graph in $\mathcal{G}_{n, m}$ for both $p\rightarrow0$ and $p\rightarrow1$. If $m\equiv 2(\bmod 3)$, we have the following theorems, whose proofs are similar to the proofs of Theorems 3.1 and 3.2.

Theorem 3.3. Let $n\geq5$ and $9\leq m\leq 3n-5$ be integers and $m\equiv 2(\bmod 3)$. Then the graph

is the locally most reliable graph in $\mathcal{G}_{n, m}$ for $p\rightarrow0$.

Theorem 3.4. Let $n\geq5$ and $9\leq m\leq 3n-5$ be integers and $m\equiv 2(\bmod 3)$. Then the graph

is the locally most reliable graph in $\mathcal{G}_{n, m}$ for $p\rightarrow1$.

Theorems $3.3$ and $3.4$ show that when $n\geq5$, $9\leq m\leq 3n-5$ and $m\equiv 2(\bmod 3)$, $B_{n, \lfloor\frac{m}{3}\rfloor+3}$ $\cup (n-\lfloor\frac{m}{3}\rfloor-3)\cdot K_1$ is the locally most reliable graph in $\mathcal{G}_{n, m}$ for both $p\rightarrow0$ and $p\rightarrow1$. Is it the uniformly most reliable graph for $11 < m \leq 3n-5$ $(n\geq5)$? In order to solve this problem, we need to compute the reliability polynomials of some three-terminal graphs.

Lemma 3.2. Let $n\geq4$ be an integer. Then

Proof. The vertices in $A_{n, 0}$ are labeled same as Figure 3. By Lemma $2.1$, we can calculate a recurrence relation for the three-terminal probability polynomial of $A_{n, 0}$.

$R_3(A_{n, 0};p) = p^3R_3(G_1;p)+p^3(1-p)R_3(G_2;p)$ + $p^2(1-p)^2R_3(G_3;p)$ + $p^3(1-p)R_3(G_4;p) +p^2(1-p)^2R_3(G_5;p)$ + $p(1-p)^2R_3(G_6;p)+p^3(1-p)R_3(G_7;p)+p^2(1-p)^2R_3(G_8;p)$ + $p(1-p)^2R_3(G_9;p) +p(1-p)^2R_3(G_{10};p)$ + $(1-p)^3R_3(G_{11};p)$, where the forms and reliability polynomials of $G_i$ ($1\leq i\leq11$) are shown in Table 1.

By Table 1, we have $R_3(A_{n, 0};p) = (1+2p)(1-p)^2R_3(A_{n-1, 0};p)+p^3(4-3p)+3p^2(1-p)^2[1-(1-p)(1-2p^2+p^3)^{n-4}]$.

Calculating the linear non-homogeneous recurrence relation, we have

The proof is completed.

Similarly as Lemma $3.2$, we can get Lemmas $3.3$ and $3.4$.

Lemma 3.3. Let $n\geq6$ and $4\leq w\leq n$ be integers. Then

Lemma 3.4. Let $n\geq6$ be an integer. Then

$R_3(A_{n, 2};p) = 3p^{10}-24p^9+80p^8-138p^7+120p^6-30p^5-28p^4+18p^3$ - $(18p^{12}-159p^{11}+603p^{10}-1272p^9+1602p^8-1173p^7+399p^6$ + $42p^5-78p^4+18p^3)(1-2p^2+p^3)^{n-6} -(3p^{10}-24p^9+81p^8-150p^7$ + $165p^6-108p^5+39p^4-6p^3)A_{n-3, 0}+(p^8-12p^7$ + $45p^6-80p^5+75p^4-36p^3+7p^2)A_{n-2, 0}$ + $(2p^5-8p^4+12p^3-8p^2+2p)A_{n-1, 0}+(p^2-2p+1)A_{n, 0}.$

With the above lemmas, we can get Theorem $3.5$.

Theorem 3.5. Let $n\geq5$ and $11 < m \leq 3n-5$ be integers and $m\equiv 2(\bmod 3)$. Then the graph $A_{\lfloor\frac{m}{3}\rfloor+2, 2}\cup (n-\lfloor\frac{m}{3}\rfloor-2)\cdot K_1$ is more reliable than $B_{n, \lfloor\frac{m}{3}\rfloor+3}\cup (n-\lfloor\frac{m}{3}\rfloor-3)\cdot K_1$ in $\mathcal{G}_{n, m}$ for $p = 1/2$.

Proof. For the convenience, let $w = \lfloor\frac{m}{3}\rfloor+3$. By Lemma $3.2$, we have

$R_3(A_{n, 0};1/2) = 1+(1/2)^{n-1}-(3/4)\cdot(5/8)^{n-3}.$

By Lemmas $3.3$ and $3.4$ and $R_3(A_{n, 0};1/2)$, we have

Thus, $R_3(A_{w-1, 2};1/2)-R_3(B_{n, w};1/2) = \frac{1}{4096}\left[46\cdot(5/8)^{w-7}-13\cdot(1/2)^{w-7}\right].$

Since $46\cdot(5/8)^{w-7} > 46\cdot(1/2)^{w-7} > 13\cdot(1/2)^{w-7}$ $(w = \lfloor\frac{m}{3}\rfloor+3\geq7)$,

$R_3(A_{w-1, 2};1/2)-R_3(B_{n, w};1/2) > 0$, which means, $R_3(A_{w-1, 2};1/2) > R_3(B_{n, w};1/2)$.

The proof is completed.

As a straightforward consequence of Theorems $3.3$ or $3.4$ and $3.5$, we obtain the following result.

Theorem 3.6. Let $n$ and $m$ be integers. If $n\geq5$, $11 < m \leq 3n-5$ and $m\equiv 2 (\bmod 3)$, then there is no uniformly most reliable graph in $\mathcal{G}_{n, m}$.

Now, the existence of uniformly most reliable graph with edges less than $3n-5$ is solved partly. How about the same question for a little more edges?

Lemma 3.5.(^[5]) Let $n\geq1$ and $0\leq m\leq n-1$ be integers.

If $m\neq3$, then the unique simple graph on $n$ vertices and $m$ edges with the maximum number of paths of length $2$ is $K_{1, m}\cup (n-m-1)\cdot K_1$.

If $m = 3$, there are two simple graphs with the maximum number of paths of length $2:$ $K_3\cup (n-3)\cdot K_1$ and $K_{1, 3}\cup (n-4)\cdot K_1$.

Theorem 3.7. Let $n\geq7$ and $3n-5 < m\leq4n-10$ be integers. Then the graph $A_{n, m-3n+6}$ is the locally most reliable graph in $\mathcal{G}_{n, m}$ for $p\rightarrow0$.

Proof. Let $G\in\mathcal{G}_{n, m}$ be the locally most reliable graph for $p\rightarrow0$. By Lemma $3.1$ and the proof of Theorem $3.1$, it is easy to see that $G$ must contain the triangle $rst$ and $n-3$ edge sets $\{rv_i, sv_i, tv_i\}$ $(4\leq i\leq n)$. Thus, we need to determine the remaining $l = m-3n+6$ edges between non-target vertices. For convenience, using $\widehat{G}$ denotes the subgraph of $G$ induced by all the non-target vertices, then $E(\widehat{G}) = l$. Since the different structures of $\widehat{G}$ may lead different $N_i$ when $i\geq4$, we begin with $N_4$, which is the number of $rst$-subgraphs with 4 edges.

The $rst$-subgraphs with $4$ edges of $G$ can be divided into two cases. Some of them is minimal and others is non-minimal. There are three forms of the minimal $rst$-subgraph with 4 edges, which are $\{sv_i, v_it, sv_j, v_jr\}$, $\{sv_i, v_iv_j, v_jt, sr\}$, and $\{sv_i, v_iv_j, v_jt, v_jr\}$ $(4\leq i, j\leq n, i\neq j)$. The number of these three edge sets is $6\binom{n-3}{2}$, $12l$ and $6l$, respectively. We can see that the number of the minimal $rst$-subgraphs with 4 edges is affected by $l$, regardless of the structure of $\widehat{G}$.

The non-minimal $rst$-subgraph with $4$ edges of $G$ include the following cases:

$C_1$: the minimal $rst$-subgraph with 2 edges,

$C_2$: the minimal $rst$-subgraph with 3 edges but no minimal $rst$-subgraph with 2 edges.

By calculation, the number of the non-minimal $rst$-subgraphs with 4 edges in $C_1$ and $C_2$ is $3\binom{m-3}{2}+(m-3)$ and $(n-3)(m-3)+6(n-3)(m-6)$, respectively. Then the number of the non-minimal $rst$-subgraphs with 4 edges is a constant for given $n$ and $m$.

Therefore, whatever the structure of $\widehat{G}$ is, $N_4$ is a constant for given $n$ and $m$. Then we need to consider $N_5$, which is the number of $rst$-subgraphs with 5 edges.

The $rst$-subgraphs with $5$ edges of $G$ can be divided into two cases. Some of them is minimal and others is non-minimal. The non-minimal $rst$-subgraph with 5 edges of $G$ include the following cases:

$D_1$: the minimal $rst$-subgraph with 2 edges,

$D_2$: the minimal $rst$-subgraph with 3 edges but no minimal $rst$-subgraph with 2 edges,

$D_3$: the minimal $rst$-subgraph with 4 edges but no minimal $rst$-subgraph with less than 4 edges.

By calculation, the number of the non-minimal $rst$-subgraphs with 5 edges in $D_1$, $D_2$ and $D_3$ is $3\binom{m-3}{3}+\binom{m-3}{2}$, $7(n-3)\binom{m-6}{2}+3(n-3)(m-6)-12\binom{n-3}{2}$ and $18l(m-10)+6l+6(m-9)\binom{n-3}{2}$, respectively. Then the number of the non-minimal $rst$-subgraphs with 5 edges is a constant for given $n$ and $m$.

There are four forms of the minimal $rst$-subgraph with 5 edges, which are $\{sv_i, v_iv_j, v_jr, rv_k$, $v_kt\}$, $\{sv_i, v_iv_j, v_jv_k, v_kt, rt\}$, $\{sv_i, v_iv_j, v_jr, v_jv_k, v_kt\}$, and $\{rv_i, sv_i, v_iv_j, v_jv_k, v_kt\}$ $(4\leq i$, $j, k\leq n, i\neq j\neq k)$. By calculation, the number of the first edge set is $12l(n-5)$, which is affected by $l$, regardless of the structure of $\widehat{G}$. But the number of other three cases affected by the number of $P_3$ in $\widehat{G}$. By Lemma $3.5$, if $l\neq3$ and $l\leq n-4$, then the number of $P_3$ in $\widehat{G}$ is maximum if $\widehat{G}$ is $K_{1, l}\cup (n-l-4)\cdot K_1$, and $G$ is $K_3\vee(K_{1, l}\cup (n-l-4)\cdot K_1)$. If $l = 3$, the number of $P_3$ in $\widehat{G}$ is maximum only if $\widehat{G}$ is either $K_3\cup (n-6)\cdot K_1$ or $K_{1, 3}\cup (n-7)\cdot K_1$, and $G$ is either $K_3\vee(K_3\cup (n-6)\cdot K_1)$ or $K_3\vee(K_{1, 3}\cup (n-7)\cdot K_1)$. Then by Lemma $3.1$, we need to compare $N_6(K_3\vee(K_3\cup (n-6)\cdot K_1))$ and $N_6(K_3\vee(K_{1, 3}\cup (n-7)\cdot K_1))$. According to the calculation method of $N_4$ and $N_5$, we can get that the difference of coefficient $N_6$s of the front two graphs is $-72$. Then for $p\rightarrow0$, $G$ is $K_3\vee(K_{1, 3}\cup (n-7)\cdot K_1)$.

From the above argument, we conclude that the graph $A_{n, m-3n+6}$ is the locally most reliable graph in $\mathcal{G}_{n, m}$ for $p\rightarrow0$.

Now, two classes of graphs are given, which will be used in the following theorems.

Let $n\geq4$ and $0\leq l\leq \lfloor\frac{n-3}{2}\rfloor$ be integers. The three-terminal graph with $n$ vertices, which is drawn as Figure 5, is denoted by $C_{n, l}$, where the vertex set $V(C_{n, l})$ is $\{r = v_1, s = v_2, t = v_3, v_4, \cdots, v_n\}$ and the edge set $E(C_{n, l})$ contains the following $3n-9+l$ edges:

Let $n\geq4$ and $0\leq l\leq n-4$ be integers. The three-terminal graph with $n$ vertices, which is drawn as Figure 5, is denoted by $C'_{n, l}$, where the vertex set $V(C'_{n, l})$ is $\{r = v_1, s = v_2, t = v_3, v_4, \cdots, v_n\}$ and the edge set $E(C'_{n, l})$ contains the following $3n-9+l$ edges:

Theorem 3.8. Let $n\geq7$ and $3n-5 < m\leq3n-6+\lfloor\frac{n-3}{2}\rfloor$ be integers. Then the graph $C_{n, m-3n+6}$ is the unique locally most reliable graph in $\mathcal{G}_{n, m}$ for $p\rightarrow1$.

Proof. Let $G\in\mathcal{G}_{n, m}$ be the unique locally most reliable graph for $p\rightarrow1$. Then by Lemma $3.1$, the value of the $rst$-edge connectivity $\lambda$ of $G$ must be as large as possible.

let $C$ be the minimal $rst$-cutset of $G$, then there must exist a component containing just one target vertex and $k$ $(0\leq k\leq n-3)$ non-target vertices $u_i$ $(1\leq i\leq k)$ in $G-C$, without loss of generality, setting this target vertex as $r$. Clearly, $\lambda\leq min\{d(r), d(s), d(t)\}\leq n-1$. If $d(r) = d(s) = d(t) = n-1$, then $|C|\geq d(r)-k+2k = d(r)+k\geq n-1$. Hence, $\lambda$ can arrive at the maximum value $n-1$ if and only if $d(r) = d(s) = d(t) = n-1$. Then, $G$ contains the triangle $rst$ and $n-3$ edge sets as $\{rv_i, sv_i, tv_i\}$ $(4\leq i\leq n)$. These $3n-6$ edges are confirmed, we also need to determine the remaining $m-3n+6$ edges connecting non-target vertices.

By Lemma $3.1$, we need to compare the number of $rst$-subgraph with $m-n+1$ edges, which is denoted as $N_{m-n+1}$, of graphs with $\lambda = n-1$. Continue to calculate the minimal $rst$-cutset of $G$, $|C| = d(r)-k+ \sum\limits_{i = 1}^k[d(u_i)-1]-2m' = n-2k-2m'-1+\sum\limits_{i = 1}^kd(u_i)$, where $m'$ is the number of edges between these $k$ non-target vertices. It is clear to see that $\sum\limits_{i = 1}^kd(u_i)\geq3k+2m'$, thus $|C|\geq n+k-1$. Then, we can get that the component of $k+1$ vertices generated by deleting the minimal $rst$-cutset of size $n-1$ contains only the target vertex. Thus, we have $N_{m-n+1} = \binom{m}{n-1}-3$, which is a constant for given $n$ and $m$. By Lemma $3.1$, we need to consider $N_{m-n}$.

The component of $k+1$ vertices generated by deleting the minimal $rst$-cutset of size $n$ contains one target vertex and one non-target vertex of degree $3$. Thus, we have $N_{m-n} = \binom{m}{n}-3\binom{m-n+1}{1}-3\binom{a}{1}$, where $a$ is the number of non-target vertices with degree $3$. Since $C_{n, m-3n+6}$ has the fewest non-target vertices with degree $3$ in graphs with $\lambda = n-1$, $N_{m-n}(C_{n, m-3n+6})$ gets the maximum value.

Therefore, $C_{n, m-3n+6}$ is the locally most reliable graph in $\mathcal{G}_{n, m}$ for $p\rightarrow1$.

Theorem 3.9. Let $n\geq7$ and $3n-6+\lfloor\frac{n-3}{2}\rfloor < m\leq4n-10$ be integers. Then the graph $C'_{n, m-3n+6}$ is more reliable than $A_{n, m-3n+6}$ in $\mathcal{G}_{n, m}$ for $p\rightarrow1$.

Proof. For convenience, let $l = m-3n+6$. In $A_{n, l}$, there are $n-4-l$ vertices of degree $3$, $l$ vertices of degree $4$, a vertex of degree $l+3$ and $3$ target vertices of degree $n-1$. And $C'_{n, l}$ has $n-4-l$ vertices of degree $3$, $2$ vertices of degree $4$, $l-1$ vertices of degree $5$ and $3$ target vertices of degree $n-1$. The $rst$-edge connectivity $\lambda$ of $A_{n, l}$ and $C'_{n, l}$ are the same, where $\lambda = n-1$.

It is easy to calculate that

$N_{m-j}(A_{n, l}) = N_{m-j}(C'_{n, l}) = \binom{m}{j}$ $(0\leq j\leq n-2)$;

$N_{m-\lambda}(A_{n, l}) = N_{m-\lambda}(C'_{n, l}) = \binom{m}{\lambda}-3$;

$N_{m-\lambda-1}(A_{n, l}) = N_{m-n}(A_{n, l}) = N_{m-\lambda-1}(C'_{n, l}) = \binom{m}{n}-3(m-l-3)$;

and

Since $l = m-3n+6\geq3$, $N_{m-\lambda-2}(C'_{n, l}) > N_{m-\lambda-2}(A_{n, l})$.

By the Lemma $3.1$, $C'_{n, m-3n+6}$ is more reliable than $A_{n, m-3n+6}$ in $\mathcal{G}_{n, m}$ for $p\rightarrow1$.

We give the locally most reliable graph in $\mathcal{G}_{n, m}$ with $3n-5 < m\leq3n-6+\lfloor\frac{n-3}{2}\rfloor$ $(n\geq7)$ for $p\rightarrow1$, as shown in Theorem $3.8$. If $3n-6+\lfloor\frac{n-3}{2}\rfloor < m\leq4n-10$ $(n\geq7)$, we construct a graph with $m$ edges that is more reliable than $A_{n, m-3n+6}$ for $p\rightarrow1$, as shown in Theorem $3.9$. Thus, we obtain the following result.

Theorem 3.10. Let $n$ and $m$ be integers. If $n\geq7$ and $3n-5 < m\leq4n-10$, then there is no uniformly most reliable graph in $\mathcal{G}_{n, m}$.

4.   Conclusions

This research focuses on characterizing the locally most reliable graph for three-terminal spare graphs. There is rare literature on the locally most reliable graph for three-terminal graphs. Based on the results of this research, the following conclusions can be drawn.

If $9\leq m\leq 3n-5$ $(n\geq5)$ and $m\equiv 2(\bmod 3)$, the locally most reliable graph for $p\rightarrow0$ and $p\rightarrow1$ are determined with theoretical proofs. It is also proved that there is no uniformly most reliable three-terminal graph when $11 < m \leq 3n-5$ $(n\geq5)$ and $m\equiv 2(\bmod 3)$.

The locally most reliable graph in $\mathcal{G}_{n, m}$ for $p\rightarrow0$ is determined with proofs when $3n-5 < m\leq4n-10$ $(n\geq7)$. The locally most reliable graph in $\mathcal{G}_{n, m}$ for $p\rightarrow1$ for $3n-5 < m\leq3n-6+\lfloor\frac{n-3}{2}\rfloor$ $(n\geq7)$ is also determined with proofs. Additionally, it is proved that there is no uniformly most reliable three-terminal graph when $3n-5 < m\leq4n-10$ $(n\geq7)$.

If $9\leq m\leq 3n-5$ $(n\geq5)$ and $m\equiv 0$ or $1(\bmod 3)$, as shown in Theorems $3.1$ and $3.2$, the locally most reliable graphs for $p\rightarrow0$ is also locally most reliable for $p\rightarrow1$. However, it is still unknown whether the locally most reliable graph is the uniformly most reliable graph for $9\leq m\leq 3n-5$ $(n\geq5)$ and $m\equiv 0$ or $1(\bmod 3)$ for all $0\leq p\leq1$.

The results of the research can be useful for designing highly reliable networks which have three target vertices. The findings of this research provide guiding significance for determining the locally most reliable graphs for general $k$-terminal networks.

Acknowledgments

Research supported by the National Science Foundation of China (Grant Nos. 11801296), the Tibetan Information Processing and Machine Translation Key Laboratory of Qinghai Province, the Science Found of Qinghai Province (Grant No. 2018-ZJ-718), the Key Laboratory of Tibetan Information Processing Ministry of Education, and Tibetan Information Processing Engineering Technology and Research Center of Qinghai Province.

Conflict of interest

The authors declare no conflict of interest in this paper.