Local Optimality of Mixed Reliability for Several Classes of Networks with Fixed Sizes

Abstract

In this work, the local optimality of mixed reliability of networks is surveyed. A reliability comparison criterion related with subgraphs to measure the local optimality of the mixed reliability of networks is established. Using the comparison criterion, we characterize all locally optimally mixed reliable networks among all n-vertex networks with fixed sizes $m=n$, $m=n+1$ and $m=n+2$, respectively.

1. Introduction

Throughout this paper, networks are modelled as graphs. All graphs considered here are simple and undirected. For positive integers m and n, an $(n,m)$ graph refers to a graph with n vertices and m edges. We shall use $\mathsf{\Omega }(n,m)$ to denote the family of all $(n,m)$ graphs. For an integer $k\ge 2$, a graph G is k-connected if, for any pair of distinct vertices s and t of G, there are at least k internally disjoint s-t paths in G. The reliability of a network is defined as the probability that the residual vertices can communicate with each other. We shall use p and q to denote probabilities, and so unless otherwise stated, p and q will denote two real numbers (or real valued functions) with $0\le p\le 1$ and $0\le q\le 1$. Generally, there are three kinds of reliability models: namely, the vertex fault model, the edge fault model, and the vertex-and-edge fault model, respectively. In the vertex fault model, it is assumed that all the edges will never fail, while the vertices could fail independently with the same failure probability p. Likewise, in the edge fault model, it is assumed that all vertices will never fail, while the edges could fail with the same failure probability q. Studies on the reliability in the vertex fault model and the edge fault model have been conducted by many researchers. In the Refs. [1,2,3], synthesis results of reliable networks in both the edge fault model and the vertex fault model were surveyed.

For the vertex fault model, Goldschmidt et al. in the Ref. [4] defined a network $G\in \mathsf{\Omega }(n,m)$ to be uniformly best if, for all choices of p, G is most reliable among all the graphs in $\mathsf{\Omega }(n,m)$, and showed that the complete bipartite graph $K_{b,b+2}$ is uniformly best among all graphs in $\mathsf{\Omega }(2b+2,b^2+2b)$. Furthermore, in the Ref. [4], the authors also showed that when $n\ge 6$, the star plus one edge and the cycle are the only two locally optimally reliable graphs of $\mathsf{\Omega }(n,n)$. Hakimi and Amin in the Ref. [5] studied the construction of reliable $(n,m)$ graphs with connectivity being $r=[2m/n]\ge 3$, and with no more than n minimum vertex cut-sets. Smith et al. [6,7] showed how to construct locally optimally reliable graphs when the probability of a vertex failure is sufficiently small.

For the edge fault model, Bauer et al. [8,9] showed that for small edge failure probabilities and given the number of vertices and edges, all graphs having minimum $m_{\lambda }$ chosen among those with maximum $\lambda$ are locally optimally reliable, and studied the existence of such graphs. Zhao [10] showed that regular complete multipartite graphs and almost regular complete multipartite graphs are locally optimally reliable in their graph classes, respectively. Boesch et al. [11] showed that, given the number of vertices n, and the number of edges m, uniformly optimally reliable simple graphs always exist for $m=n-1,n,n+1$, or $n+2$, and proposed a conjecture for $m=n+3$. Gross et al. [12] demonstrated that the uniformly optimally reliable simple graphs in these classes in the Ref. [11] were also uniformly optimally reliable when the classes were extended to include multigraphs. Wang [13] gave a proof of Boesch’s conjecture in the Ref. [11]. In the Ref. [14], the uniformly optimally and least reliable networks were given for the families of networks with n vertices, $n+1$ and $n+2$ edges. Liu et al. [15] proved that for any positive integer b, the complete tripartite graph $K(b,b+1,b+2)$ is uniformly optimally reliable in its class $\mathsf{\Omega }(3b+3,3b^2+6b+2)$. In 2014, Brown et al. [16] proved that uniformly optimally reliable graphs do not always exist. Petingi et al. [17] characterized uniformly least reliable graphs for m greater than or equal to $(n-1)(n-2)/2+1$. In the Ref. [18], the synthesis results of reliable networks were reviewed. Boesch et al. ([11]), Gross and Saccoman ([12]), and Chen and Zhao ([14]) also investigated the edge fault model, and independently verified the existence of uniformly optimally reliable graphs in the families of graphs $\mathsf{\Omega }(n,n)$, $\mathsf{\Omega }(n,n+1)$ and $\mathsf{\Omega }(n,n+2)$. Nevertheless, Goldschmidt et al. in the Ref. [4] showed that with the vertex fault model, the above three families of graphs do not contain uniformly optimally reliable graphs.

Naturally, the vertex-and-edge fault model generalizes the two models above. In the vertex-and-edge fault model, it is assumed that the vertices would fail independently with probability p, and the edges would fail independently with probability q.

For the vertex-and-edge fault model, Evans and Smith [19] made a connection between the following two cases: small p, $q=0$ and small q, $p=0$. Smith [20] showed that when p and q are small, a small-mixed-cut-set-optimal graph has the minimum unconnected probability among the graphs with given numbers of vertices and edges, and gave the method of how to construct these optimal graphs in many cases. Chen and He [21] in 2004 gave the upper and lower bounds of the mixed reliability of networks with unreliable vertices and edges. Mohamed [22] presented a new approach by using an efficient algorithm for evaluating the upper bound of the residual connectedness reliability of distributed systems with unreliable vertices and edges. For the case of the k-terminal connectivity criterion, Shpung, in the Ref. [23], used a Monte Carlo scheme to evaluate reliability for the networks with unreliable vertices and edges. Dash [24] used the artificial neural network in solving the network reliability optimization problem subjected to some total cost of the network, considering both edges and vertices of the network to be imperfect.

To the best of our knowledge, local optimality in mixed reliable networks has not been fully investigated. This motivates our current research. It has been known that the failure probabilities p and q are very small in real-life networks. Thus, the case when both p and q are close to 0 becomes very significant in practical applications. In this work, a reliability comparison criterion was established utilizing parameters related with subgraphs to measure the local optimality of the mixed reliability of networks. Using this comparison criterion, we characterize all locally optimally mixed reliable networks in $\mathsf{\Omega }(n,n+k)$ with $k\le 2$. Preliminaries will be shown in the next section. The comparison criterion is presented in Section 3. The characterizations of the locally optimally mixed reliable networks are obtained in the last two sections.

2. Preliminaries

Let $G=(V,E)$ be a $(n,m)$ graph with vertex set V and edge set E. In the edge fault model, the reliability of G [17] is defined by

$$R(G,q)=\sum _{\ell =n-1}^m{N}_{\ell }\left(G\right)q^{m-\ell }{(1-q)}^{\ell },$$

where for all ℓ with $n-1\le \ell \le m$, $N_{\ell }\left(G\right)$ is the number of connected spanning subgraphs with ℓ edges of G.

Let i and j be integers with $0\le i\le \left|V\right|$ and $0\le j\le \left|E\right|$. For a vertex subset $V_1\subseteq V$ and an edge subset $E_1\subseteq E$ with $|V_1|=i,|E_1|=j$, let $G-V_1-E_1$ denote the subgraph obtained from G by deleting all vertices in $V_1$ and all edges in $E_1$. If $G-V_1-E_1$ is disconnected, then $(V_1,E_1)$ is said to be an i-j mixed cut set of G. Let $M_{ij}\left(G\right)$ denote the number of i-j mixed cut sets in a graph G. It is shown in the Ref. [20] that, in the vertex-and-edge fault model, the disconnected probability of G, denoted by $P(G;p,q)$, can be expressed as

$$P(G;p,q)=\sum _{i=0}^n\sum _{j=0}^m{M}_{ij}\left(G\right)p^i{(1-p)}^{n-i}{q}^j{(1-q)}^{m-j}.$$

The mixed reliability of G is defined as $R(G;p,q)=1-P(G;p,q)$. The two polynomials $P(G;p,q)$ and $R(G;p,q)$ are also called the mixed unreliability polynomial and the mixed reliability polynomial of G, respectively. Clearly, $R(G;p,q)$ is a function on p and q.

Motivated by the definition of locally optimally reliable networks in the vertex fault model defined in the Ref. [4], we propose the following definition of locally optimally mixed reliable networks in the vertex-and-edge fault model.

Let $p,q$ denote two real numbers with $0\le p\le 1$ and $0\le q\le 1$. When $p=0$ and $q=0$, for a positive number $\delta$, define $U((0,0),\delta )=\left\{(x,y)\right|\sqrt{x^2+y^2}<\delta \}$.

Definition 1.

A graph G in $\mathsf{\Omega }(m,n)$ is called locally optimally mixed reliable at $(0,0)$, if there exists a real number $\epsilon >0$ such that the mixed reliability of G is greater than or equal to that of all other graphs in $\mathsf{\Omega }(n,m)$ for all two-tuples $(p,q)\in U((0,0),\epsilon )\cap {[0,1]}^2$.

3. Local Optimality of Mixed Reliability of Networks

For a graph $G\in \mathsf{\Omega }(n,m)$ and an integer $i\ge 1$, let ${\mathcal{H}}_G^{\left(i\right)}$ denote the set of all connected subgraphs induced by i vertices of G, and $s_i\left(G\right)$ be the number of connected induced subgraphs of G with i vertices. To emphasize the graph G, we often used $n\left(G\right)$ and $m\left(G\right)$ to denote the number of vertices and the number of edges of G, respectively. For an integer $k\ge 1$, the parameter $I_k\left(G\right)$ of a graph G, which depends on the subgraphs of G, is defined as follows.

$$I_k\left(G\right)=\left|\right\{(S,F)|S\subseteq V\left(G\right),F\subseteq E(G-S),\left|S\right|+\left|F\right|=k\mathrm{and}G-S-F\mathrm{is}\mathrm{connected}\left\}\right|.$$

When $k=1,2$, we have

$$I_1\left(G\right)=N_{m-1}\left(G\right)+s_{n-1}\left(G\right)$$

(1)

and

$$I_2\left(G\right)=N_{m-2}\left(G\right)+s_{n-2}\left(G\right)+\sum _{H\in {\mathcal{H}}_G^{(n-1)}}{N}_{m\left(H\right)-1}\left(H\right).$$

(2)

Using the parameters above, a reliability comparison criterion is established to determine which graph is more locally mixed and reliable between any two $(n,m)$ graphs. Lemma 1 presents a formula to calculate the mixed reliability polynomial of networks.

Lemma 1.

Let G be a graph in $\mathsf{\Omega }(n,m)$ and ${\mathcal{H}}_G$ be the set of all connected induced subgraphs H of G ([10]). Then

$$R(G;p,q)=\sum _{H\in {\mathcal{H}}_G}{p}^{n-n\left(H\right)}{(1-p)}^{n\left(H\right)}R(H,q).$$

Theorem 1.

Let n and m be two positive integers and let G and $G^{\prime }$ be two graphs in $\mathsf{\Omega }(n,m)$. Suppose that in the process of $q\to 0$, there exist two positive real numbers $c_1$ and $c_2$ such that $c_{1}q\le p\le c_{2}q$. If (a) $I_1\left(G\right)>I_1\left(G^{\prime }\right)$, or (b) $I_1\left(G\right)=I_1\left(G^{\prime }\right)$ and $I_2\left(G\right)>I_2\left(G^{\prime }\right)$, then $R(G;p,q)>R(G^{\prime };p,q)$.

Proof. 

By assumption, in the process of $q\to 0$, there exist two positive real numbers $c_1$ and $c_2$ such that $c_{1}q\le p\le c_{2}q$, and it follows that

$$q^2=o\left(q\right),p^2=o\left(q\right),pq=o\left(q\right)\mathrm{and}{q}^3=o\left(q^2\right),p^3=o\left(q^2\right),p^{2}q=o\left(q^2\right),p{q}^2=o\left(q^2\right).$$

(3)

As $G\in \mathsf{\Omega }(n,m)$, by Lemma 1, we have

$$\begin{array}{cc}\hfill R(G;p,q)& =\sum _{H\in {\mathcal{H}}_G}{p}^{n-n\left(H\right)}{(1-p)}^{n\left(H\right)}R(H,q)\hfill \\ \hfill & =\sum _{i=1}^n{(1-p)}^i{p}^{n-i}\sum _{H\in {\mathcal{H}}_G^{\left(i\right)}}\sum _{j=i-1}^{m\left(H\right)}{N}_j\left(H\right)q^{m\left(H\right)-j}{(1-q)}^j\hfill \\ \hfill & =\sum _{i=1}^n{(1-p)}^i{p}^{n-i}\sum _{k=0}^{m_G^{\left(i\right)}-i+1}[\sum _{H\in {\mathcal{H}}_G^{\left(i\right)}}{N}_{m\left(H\right)-k}\left(H\right){(1-q)}^{m\left(H\right)-k}]q^k,\hfill \end{array}$$

where $m_G^{\left(i\right)}=max\{m\left(H\right)|H\in {\mathcal{H}}_G^{\left(i\right)}\}$. Define

$$h_{i,k}\left(G\right)=\sum _{H\in {\mathcal{H}}_G^{\left(i\right)}}{N}_{m\left(H\right)-k}\left(H\right){(1-q)}^{m\left(H\right)-k},$$

where $h_{i,k}\left(G\right)$ is a polynomial on $1-q$. Note that for any i, we have $\underset{q\to 0}{lim}{h}_{i,0}\left(G\right)=s_i\left(G\right)$ and $\underset{q\to 0}{lim}{h}_{n,i}\left(G\right)=N_{m-i}\left(G\right)$. Therefore, using (3), we can write $R(G;p,q)$ as follows.

$$\begin{array}{ccc}\hfill R(G;p,q)& =& {\displaystyle \sum _{i=3}^n}{(1-p)}^i{p}^{n-i}{\displaystyle \sum _{k=0}^{m_G^{\left(i\right)}-i+1}}{h}_{i,k}\left(G\right)q^k+m{(1-p)}^2{p}^{n-2}(1-q)+n(1-p)p^{n-1}\hfill \\ \hfill & =& {(1-p)}^n{h}_{n,0}\left(G\right)+{(1-p)}^{n}q{h}_{n,1}\left(G\right)+{(1-p)}^{n-1}p{h}_{n-1,0}\left(G\right)+o\left(q\right).\hfill \end{array}$$

(4)

Likewise, as $G^{\prime }\in \mathsf{\Omega }(n,m)$, we have

$$\begin{array}{ccc}\hfill R(G^{\prime };p,q)& =& {\displaystyle \sum _{i=3}^n}{(1-p)}^i{p}^{n-i}{\displaystyle \sum _{k=0}^{m_{G^{\prime }}^{\left(i\right)}-i+1}}{h}_{i,k}\left(G^{\prime }\right)q^k+m{(1-p)}^2{p}^{n-2}(1-q)+n(1-p)p^{n-1}\hfill \\ \hfill & =& {(1-p)}^n{h}_{n,0}\left(G^{\prime }\right)+{(1-p)}^{n}q{h}_{n,1}\left(G^{\prime }\right)+{(1-p)}^{n-1}p{h}_{n-1,0}\left(G^{\prime }\right)+o\left(q\right).\hfill \end{array}$$

(5)

Direct computation utilizing (4) and (5) yields the following:

$$\begin{array}{cc}\hfill & \underset{q\to 0}{lim}\frac{R(G;p,q)-{(1-p)}^n{h}_{n,0}\left(G\right)}{R(G^{\prime };p,q)-{(1-p)}^n{h}_{n,0}\left(G^{\prime }\right)}\hfill \\ \hfill =& \underset{q\to 0}{lim}\frac{{(1-p)}^{n}q{h}_{n,1}\left(G\right)+{(1-p)}^{n-1}p{h}_{n-1,0}\left(G\right)+o\left(q\right)}{{(1-p)}^{n}q{h}_{n,1}\left(G^{\prime }\right)+{(1-p)}^{n-1}p{h}_{n-1,0}\left(G^{\prime }\right)+o\left(q\right)}\hfill \\ \hfill =& \underset{q\to 0}{lim}\frac{h_{n,1}\left(G\right)+h_{n-1,0}\left(G\right)}{h_{n,1}\left(G^{\prime }\right)+h_{n-1,0}\left(G^{\prime }\right)}\hfill \\ \hfill =& \frac{N_{m-1}\left(G\right)+s_{n-1}\left(G\right)}{N_{m-1}\left(G^{\prime }\right)+s_{n-1}\left(G^{\prime }\right)}\hfill \\ \hfill =& \frac{I_1\left(G\right)}{I_1\left(G^{\prime }\right)}.\hfill \end{array}$$

It follows that if $I_1\left(G\right)>I_1\left(G^{\prime }\right)$, then we have $R(G;p,q)>R(G^{\prime };p,q)$.

For the case of $I_1\left(G\right)=I_1\left(G^{\prime }\right)$, since $\underset{q\to 0}{lim}{h}_{n-1,1}\left(G\right)={\displaystyle \sum _{H\in {\mathcal{H}}_G^{(n-1)}}}{N}_{m\left(H\right)-1}\left(H\right)$, we similarly have

$$\begin{array}{cc}\hfill & \underset{q\to 0}{lim}\frac{R(G;p,q)-{(1-p)}^n[h_{n,0}\left(G\right)+q{h}_{n,1}\left(G\right)]-{(1-p)}^{n-1}p{h}_{n-1,0}\left(G\right)}{R(G^{\prime };p,q)-{(1-p)}^n[h_{n,0}\left(G^{\prime }\right)+q{h}_{n,1}\left(G^{\prime }\right)]-{(1-p)}^{n-1}p{h}_{n-1,0}\left(G^{\prime }\right)}\hfill \\ \hfill =& \underset{q\to 0}{lim}\frac{{(1-p)}^n{q}^2{h}_{n,2}\left(G\right)+{(1-p)}^{n-1}pq{h}_{n-1,1}\left(G\right)+{(1-p)}^{n-2}{p}^2{h}_{n-2,0}\left(G\right)+o\left(q^2\right)}{{(1-p)}^n{q}^2{h}_{n,2}\left(G^{\prime }\right)+{(1-p)}^{n-1}pq{h}_{n-1,1}\left(G^{\prime }\right)+{(1-p)}^{n-2}{p}^2{h}_{n-2,0}\left(G^{\prime }\right)+o\left(q^2\right)}\hfill \\ \hfill =& \underset{q\to 0}{lim}\frac{h_{n,2}\left(G\right)+h_{n-1,1}\left(G\right)+h_{n-2,0}\left(G\right)}{h_{n,2}\left(G^{\prime }\right)+h_{n-1,1}\left(G^{\prime }\right)+h_{n-2,0}\left(G^{\prime }\right)}\hfill \\ \hfill =& \frac{N_{m-2}\left(G\right)+{\displaystyle \sum _{H\in {\mathcal{H}}_G^{(n-1)}}}{N}_{m\left(H\right)-1}\left(H\right)+s_{n-2}\left(G\right)}{N_{m-2}\left(G^{\prime }\right)+{\displaystyle \sum _{H\in {\mathcal{H}}_{G^{\prime }}^{(n-1)}}}{N}_{m\left(H\right)-1}\left(H\right)+s_{n-2}\left(G^{\prime }\right)}\hfill \\ \hfill =& \frac{I_2\left(G\right)}{I_2\left(G^{\prime }\right)}.\hfill \end{array}$$

It follows that if $I_1\left(G\right)=I_1\left(G^{\prime }\right)$ and $I_2\left(G\right)>I_2\left(G^{\prime }\right)$, then $R(G;p,q)>R(G^{\prime };p,q)$. □

As a consequence of the definition of $I_1\left(G\right)$, we observe that

Theorem 2.

For any $G\in \mathsf{\Omega }(n,m)$, $I_1\left(G\right)\le n+m$. Furthermore, $I_1\left(G\right)=n+m$ if and only if G is 2-connected.

4. Locally Optimally Mixed Reliable Networks in $\mathsf{\Omega }(\mathit{n},\mathit{n})$ and $\mathsf{\Omega }(\mathit{n},\mathit{n}+\mathbf{1})$

As any connected graph $G\in \mathsf{\Omega }(n,n)$ must be a graph with a unique cycle, a locally optimally mixed reliable graph is the cycle $C_n$ with n vertices. Thus, we consider graphs in $\mathsf{\Omega }(n,n+1)$.

A chain in a graph is a path, each of whose internal vertex has a degree of exactly two in G and each of whose end vertices is of a degree larger than two. If two or more chains share the same two ends, then we say that these chains are parallel chains. The number of edges on a chain is called the length of the chain. For given positive integers $a,b$ and c, let $\theta (a,b,c)$ denote the graph consisting of three parallel chains with lengths being $a,b$, and c, respectively, as depicted in Figure 1.

Define $\mathsf{\Theta }\left(n\right)=\left\{\theta \right(a,b,c\left)\right|a\ge b\ge c\ge 1\mathrm{and}a+b+c=n+1\}$. It is routine to verify that $\mathsf{\Theta }\left(n\right)$ is the only class of 2-connected graphs in $\mathsf{\Omega }(n,n+1)$.

As shown in the next theorem, the following subfamily of $\mathsf{\Theta }\left(n\right)$ is of particular interest:

$${\mathsf{\Theta }}^{\prime }\left(n\right)=\left\{\theta (a,b,c)\right|a\ge b\ge c\ge 1,max\{a-b,b-c,a-c\}\le 1\mathrm{and}a+b+c=n+1\}.$$

(6)

Theorem 3.

A graph $G\in \mathsf{\Omega }(n,n+1)$ is a locally optimally mixed reliable network at $(0,0)$ if and only if $G\in {\mathsf{\Theta }}^{\prime }\left(n\right)$.

Proof. 

We first prove the necessity, and assume that $G\in \mathsf{\Omega }(n,n+1)$ is locally optimally mixed reliable at $(0,0)$. By Theorems 1 and 2, we conclude that G lies in $\mathsf{\Theta }\left(n\right)$. Thus, there exist some integers $a\ge b\ge c\ge 1$ with $a+b+c=n+1$ such that $G=\theta (a,b,c)$. Let $\theta =\theta (a,b,c)$. Then, $N_{m-2}\left(\theta \right)$ is equal to the number of ways of removing one edge from any two of the three chains, respectively. Thus, $N_{m-2}\left(\theta \right)=ab+bc+ca$. If the graph obtained by removing two vertices of $\theta (a,b,c)$ is connected, then there are two different cases below.

Case 1. Remove two adjacent vertices in one chain. The numbers of ways for such a removal are m and $m-1$ in the cases of $c\ne 1$ and $c=1$, respectively.

Case 2. Remove one vertex of degree 2 from two chains, respectively. The number of ways for such removal is $(a-1)(b-1)+(b-1)(c-1)+(c-1)(a-1)$.

Summing up the two cases above, we have

$$s_{n-2}\left(\theta \right)=\left\{\begin{array}{cc}ab+bc+ca-m+3\hfill & ifc\ne 1,\hfill \\ ab+bc+ca-m+2\hfill & ifc=1.\hfill \end{array}\right.$$

Note that ${\displaystyle \sum _{H\in {\mathcal{H}}_{\theta }^{(n-1)}}}{N}_{m\left(H\right)-1}\left(H\right)$ is equal to the number of ways to remove one vertex of degree 2 from one chain and one edge from another one. Hence, direct computation yields

$$\sum _{H\in {\mathcal{H}}_{\theta }^{(n-1)}}{N}_{m\left(H\right)-1}\left(H\right)=(a-1)(b+c)+(b-1)(a+c)+(c-1)(a+b).$$

It follows that $I_2\left(\theta \right)$ can be expressed as follows.

$$I_2\left(\theta \right)=\left\{\begin{array}{cc}4(ab+bc+ca)-3m+3\hfill & ifc\ne 1,\hfill \\ 4(ab+bc+ca)-3m+2\hfill & ifc=1.\hfill \end{array}\right.$$

(7)

By (7), we have

$$I_2\left[\theta (a-1,b,c+1)\right]-I_2\left[\theta (a,b,c)\right]=\left\{\begin{array}{cc}4(a-c-1)\hfill & ifc\ne 1,\hfill \\ 4(a-c-1)+1\hfill & ifc=1.\hfill \end{array}\right.$$

As $a-c\ge 2$, we conclude that $I_2\left[\theta (a-1,b,c+1)\right]-I_2\left[\theta (a,b,c)\right]>0$. Therefore, if $I_2\left(G\right)$ is with the maximum value among all $G\in \mathsf{\Theta }\left(n\right)$, then we must have $max\{a-b,b-c,a-c\}\le 1$, and so $G\in {\mathsf{\Theta }}^{\prime }\left(n\right)$. This completes the proof for the necessity.

To show the sufficiency, we assume that $G\in {\mathsf{\Theta }}^{\prime }\left(n\right)$. Hence, by (6), there exists integers $a,b$ and c with $a\ge b\ge c\ge 1,max\{a-b,b-c,a-c\}\le 1$ and $a+b+c=n+1$, and with $m=\left|E\right(G\left)\right|=n+1$. It follows by (1) that $I_1\left(G\right)=n+m$, and so by Theorem 2, $I_1\left(G\right)=max\left\{I_1\left(H\right)\right|H\in \mathsf{\Omega }(n,n+1)\}$. Since $max\{a-b,b-c,a-c\}\le 1$, it follows from (7) that $I_2\left(G\right)=max\left\{I_2\left(H\right)\right|H\in \mathsf{\Omega }(n,n+1)\}$. It then follows by Theorem 1 that G is a locally optimally mixed reliable network at $(0,0)$. □

5. Locally Optimally Mixed Reliable Networks in $\mathsf{\Omega }(\mathit{n},\mathit{n}+\mathbf{2})$

Chen and Zhao [14] showed that there are only four classes of 2-connected graphs in $\mathsf{\Omega }(n,n+2)$, denoted by ${\mathcal{F}}_1\left(n\right)$, ${\mathcal{F}}_2\left(n\right)$, ${\mathcal{F}}_3\left(n\right)$ and ${\mathcal{F}}_4\left(n\right)$, respectively. To present the definitions of these graph families, we firstly introduce some notations. Let $a,b,c,d,e,f,e_1,e_2$ be positive integers. We define the graphs $F_1(a,b,c,d,e,f)$, $F_2(a,b,c,d,e_1,e_2)$, $F_3(a,b,c,d,e)$, $F_4(a,b,c,d)$ as illustrated in Figure 2, respectively, where a dotted line in the graph represents a chain of the given length. Then we can define the related graph families as shown below.

$$\begin{array}{cc}\hfill {\mathcal{F}}_1\left(n\right)& =\left\{F_1(a,b,c,d,e,f)\right|a+b+c+d+e+f=n+2anda,b,c,d,e,f\ge 1\},\hfill \\ \hfill {\mathcal{F}}_2\left(n\right)& =\left\{F_2(a,b,c,d,e_1,e_2)\right|a+b+c+d+e_1+e_2=n+2\hfill \\ \hfill & anda,b,c,d,e_1,e_2\ge 1\},\hfill \\ \hfill {\mathcal{F}}_3\left(n\right)& =\left\{F_3(a,b,c,d,e)\right|a+b+c+d+e=n+2anda,b,c,d,e\ge 1\},\hfill \\ \hfill {\mathcal{F}}_4\left(n\right)& =\left\{F_4(a,b,c,d)\right|a+b+c+d=n+2anda,b,c,d\ge 1\}.\hfill \end{array}$$

The purpose of this section is to characterize networks in $\mathsf{\Omega }(n,n+2)$ that are locally optimally mixed reliable at $(0,0)$. We firstly investigate the necessity. By Theorems 1 and 2, if $G\in \mathsf{\Omega }(n,n+2)$ is locally optimally mixed reliable at $(0,0)$, then G belongs to one of these graph families: $\{{\mathcal{F}}_1\left(n\right),{\mathcal{F}}_2\left(n\right),{\mathcal{F}}_3\left(n\right),{\mathcal{F}}_4\left(n\right)\}.$ Lemma 2 below investigates the locally optimally mixed reliable networks in ${\mathcal{F}}_1\left(n\right)$. For notational convenience, we denote $F_1=F_1(a,b,c,d,e,f)$.

Lemma 2.

If $F_1\in {\mathcal{F}}_1\left(n\right)$ is a locally optimally mixed reliable network at $(0,0)$, then for any two numbers $x,y\in \{a,b,c,d,e,f\}$, we have $|x-y|\le 1$.

Proof. 

Suppose $m=n+2$. The formula for $I_2\left(F_1\right)$ is obtained from the following three cases.

Case 1. Remove two edges of $F_1$. Since $N_{m-2}\left(F_1\right)$ is equal to the number of ways of removing one edge from any two chains, respectively, we have

$$N_{m-2}\left(F_1\right)=ab+ac+ad+ae+af+bc+bd+be+bf+cd+ce+cf+de+df+ef.$$

Case 2. Remove two vertices of $F_1$. If the graph obtained by removing two vertices of $F_1$ is connected, then there are three subcases below.

Subcase 2.1. Remove two adjacent vertices in one chain. The number of ways for such removal is m.

Subcase 2.2. Remove one vertex of degree 2 from two chains, respectively. The number of ways for such removal is $ab+ac+ad+ae+af+bc+bd+be+bf+cd+ce+cf+de+df+ef-5m+15$.

Subcase 2.3. Remove a vertex of degree 3 and a vertex of degree 2 such that the graph obtained is also connected. The number of ways for such removal is $2m-12$.

By computation, we obtain

$$\begin{array}{ccc}\hfill s_{n-2}\left(F_1\right)& =& ab+ac+ad+ae+af+bc+bd+be+bf\hfill \\ & & +cd+ce+cf+de+df+ef-2m+3.\hfill \end{array}$$

Case 3. Remove a vertex and an edge of $F_1$. If the graph obtained from $F_1$ by removing a vertex and an edge (which is not incident with the vertex removed) is connected, then there are two subcases below.

Subcase 3.1. Remove a vertex of degree 2 from one chain and an edge from another one. The number of ways for such removal is $2(ab+ac+ad+ae+af+bc+bd+be+bf+cd+ce+cf+de+df+ef)-5m$.

Subcase 3.2. Remove a vertex of degree 3 and an edge from the chain not containing the removed vertex. Then the number of ways for such removal is $2m$. Thus, we have

$$\begin{array}{ccc}\hfill \sum _{H\in {\mathcal{H}}_{F_1}^{(n-1)}}{N}_{m\left(H\right)-1}\left(H\right)& =& 2(ab+ac+ad+ae+af+bc+bd+be+bf\hfill \\ & & +cd+ce+cf+de+df+ef)-3m.\hfill \end{array}$$

This leads to the following.

$$\begin{array}{ccc}\hfill I_2\left(F_1\right)& =& 4(ab+ac+ad+ae+af+bc+bd+be+bf\hfill \\ \hfill & & +cd+ce+cf+de+df+ef)-5m+3.\hfill \end{array}$$

(8)

By (8), the following inequalities hold. If the largest difference for the lengths of any two chains with a common vertex is at least 2, say $a-b\ge 2$, then

$$I_2\left[F_1(a-1,b+1,c,d,e,f)\right]-I_2\left[F_1(a,b,c,d,e,f)\right]=4(a-b-1)>0.$$

If the largest difference for the lengths of any two chains without a common vertex is at least 2, say $a-d\ge 2$, then

$$I_2\left[F_1(a-1,b,c,d+1,e,f)\right]-I_2\left[F_1(a,b,c,d,e,f)\right]=4(a-d-1)>0.$$

Hence, if $I_2\left(F_1\right)$ reaches the maximum value among all $F_1\in {\mathcal{F}}_1\left(n\right)$, then for any two numbers $x,y\in \{a,b,c,d,e,f\}$, we have $|x-y|\le 1$. □

Suppose $F_2=F_2(a,b,c,d,e_1,e_2)$ and $a\ge c$, $b\ge d$, $e_1\ge e_2$. Let $m=n+2$. In order to obtain the formula for $I_2\left(F_2\right)$, the following three cases need to be discussed.

Case 1. Remove two edges of $F_2$. Note that $N_{m-2}\left(F_2\right)$ is equal to the number of ways to remove two edges of $F_2$ such that the graph obtained from $F_2$ by removing these edges is connected. Then we have

$$N_{m-2}\left(F_2\right)=ab+ac+ad+a{e}_1+a{e}_2+bc+bd+b{e}_1+b{e}_2+cd+c{e}_1+c{e}_2+d{e}_1+d{e}_2.$$

Case 2. Remove two vertices of $F_2$. If the graph obtained from $F_2$ by removing two vertices is connected, then there are three subcases below.

Subcase 2.1. Remove two adjacent vertices in one chain. Thus, the numbers of ways for such removal may be m, $m-1$, and $m-2$, respectively.

Subcase 2.2. Remove a vertex of degree 2 from two different chains, respectively. The number of ways for such removal is $ab+ac+ad+a{e}_1+a{e}_2+bc+bd+b{e}_1+b{e}_2+cd+c{e}_1+c{e}_2+d{e}_1+d{e}_2-5m+e_1+e_2+14$.

Subcase 2.3. Remove a vertex of degree 3 and a vertex of degree 2, respectively. The number of ways for such removal is $2(a+b+c+d-4)$. By computation, we get

$$\begin{array}{ccc}\hfill s_{n-2}\left(F_2\right)& =& ab+ac+ad+a{e}_1+a{e}_2+bc+bd+b{e}_1+b{e}_2\hfill \\ & & +cd+c{e}_1+c{e}_2+d{e}_1+d{e}_2-2m-e_1-e_2+k,\hfill \end{array}$$

where $k=\left\{\begin{array}{cc}6\hfill & ifc,d\ne 1,\hfill \\ 5\hfill & ifonlyoneofcanddis1,\hfill \\ 4\hfill & ifc=d=1.\hfill \end{array}\right.$

Case 3. Remove a vertex and an edge of $F_2$. If the graph obtained from $F_2$ by removing a vertex and an edge (which is not incident with the vertex removed) is connected, then there are two subcases below.

Subcase 3.1. Remove a vertex of degree 2 in one chain of $F_2$ and remove an edge in another chain. The number of ways for such removal is $(a-1)(m-a)+(b-1)(m-b)+(c-1)(m-c)+(d-1)(m-d)+(e_1-1)(a+b+c+d)+(e_2-1)(a+b+c+d)$.

Subcase 3.2. Remove a vertex of degree 3 of $F_2$ and remove an edge in one chain. The number of ways for such removal is $2(a+b+c+d)$.

Thus, we have

$$\begin{array}{ccc}\hfill \sum _{H\in {\mathcal{H}}_{F_2}^{(n-1)}}{N}_{m\left(H\right)-1}\left(H\right)& =& 2(ab+ac+ad+a{e}_1+a{e}_2+bc+bd+b{e}_1+b{e}_2\hfill \\ & & +cd+c{e}_1+c{e}_2+d{e}_1+d{e}_2)-3m-e_1-e_2.\hfill \end{array}$$

By computation, the formula for $I_2\left(F_2\right)$ is given by

$$\begin{array}{ccc}\hfill I_2\left(F_2\right)& =& 4(ab+ac+ad+a{e}_1+a{e}_2+bc+bd+b{e}_1+b{e}_2\hfill \\ & & +cd+c{e}_1+c{e}_2+d{e}_1+d{e}_2)-5m-2(e_1+e_2)+k,\hfill \end{array}$$

(9)

where $k=\left\{\begin{array}{cc}6\hfill & ifc,d\ne 1,\hfill \\ 5\hfill & ifonlyoneofcanddis1,\hfill \\ 4\hfill & ifc=d=1.\hfill \end{array}\right.$

Assume that $F_3=F_3(a,b,c,d,e)$ with $a\ge c$, $b\ge d$. Let $m=n+2$. By (9), in the case of $e_1=e$ and $e_2=0$, we obtain

$$I_2\left(F_3\right)=4(ab+ac+ad+ae+bc+bd+be+cd+ce+de)-5m-2e+k,$$

(10)

where $k=\left\{\begin{array}{cc}6\hfill & ifc,d\ne 1,\hfill \\ 5\hfill & ifonlyoneofcanddis1,\hfill \\ 4\hfill & ifc=d=1.\hfill \end{array}\right.$

Assume that $F_4=F_4(a,b,c,d)$ with $a\ge b\ge c\ge d$. Let $m=n+2$. By the same reason, we have

$$I_2\left(F_4\right)=\left\{\begin{array}{cc}4(ab+ac+ad+bc+bd+cd)-5m+6\hfill & ifd\ne 1,\hfill \\ 4(ab+ac+ad+bc+bd+cd)-5m+5\hfill & ifd=1.\hfill \end{array}\right.$$

(11)

By comparing $I_2\left(F_1\right)$, $I_2\left(F_2\right)$, $I_2\left(F_3\right)$ and $I_2\left(F_4\right)$, by (8)–(11), we have the following.

Lemma 3.

For $F_4(a,b,c,d)\in {\mathcal{F}}_4\left(n\right)$ and $a\ge 2$, then

$$I_2\left[F_3(a-1,b,c,d,1)\right]-I_2\left[F_4(a,b,c,d)\right]>0.$$

Lemma 4.

For $F_3(a,b,c,d,e)\in {\mathcal{F}}_3\left(n\right)$ and $a\ge 2$, then

$$I_2\left[F_1(a-1,b,c,d,e,1)\right]-I_2\left[F_3(a,b,c,d,e)\right]>0.$$

Lemma 5.

For $F_2(a,b,c,d,e_1,e_2)\in {\mathcal{F}}_2\left(n\right)$, then

$$I_2\left[F_3(a,b,c,d,e_1+e_2)\right]=I_2\left[F_2(a,b,c,d,e_1,e_2)\right].$$

Motivated by the discussions above, we define a subfamily of ${\mathcal{F}}_1\left(n\right)$ as follows.

$${\mathcal{F}}_1^{\prime }\left(n\right)=\{F_1(a,b,c,d,e,f)\in {\mathcal{F}}_1\left(n\right)|\mathrm{for}\mathrm{any}x,y\in \{a,b,c,d,e,f\},|x-y|\le 1\}.$$

By Lemmas 3–5, we conclude that if $I_2\left(G\right)$ is with the maximum value among all $G\in \mathsf{\Omega }(n,n+2)$, then G is a member in ${\mathcal{F}}_1\left(n\right)$. By Lemma 2, it holds that:

Lemma 6.

If $G\in \mathsf{\Omega }(n,n+2)$ is the locally optimally mixed reliable network at $(0,0)$, then $G\in {\mathcal{F}}_1^{\prime }\left(n\right)$.

Theorem 4.

A graph $G\in \mathsf{\Omega }(n,n+2)$ is a locally optimally mixed reliable network at $(0,0)$ if and only if $G\in {\mathcal{F}}_1^{\prime }\left(n\right)$.

Proof. 

As Lemma 6 justifies the necessity of the theorem, it suffices to prove the sufficiency. Suppose that $G\in {\mathcal{F}}_1^{\prime }\left(n\right)$. Then $G=F_1(a,b,c,d,e,f)$ for some positive integers $a,b,c,d,e,f$, satisfying $a+b+c+d+e+f=n+2$ such that any two of $\{a,b,c,d,e,f\}$ differ by one at most. With $m=\left|E\right(G\left)\right|=n+2$, it follows by (1) that $I_1\left(G\right)=n+m$, and so by Theorem 2, $I_1\left(G\right)=max\left\{I_1\left(H\right)\right|H\in \mathsf{\Omega }(n,n+2)\}$. Since any two of $\{a,b,c,d,e,f\}$ differ by at most one, by (8), we conclude that $I_2\left(G\right)=max\left\{I_2\left(H\right)\right|H\in \mathsf{\Omega }(n,n+2)\}$ as well. Now by Theorem 1, G is a locally optimally mixed reliable network at $(0,0)$, and so the sufficiency is also proved. □

6. Conclusions

The reliability of networks has become increasingly important, as the number of network applications in critical infrastructure and other social and management areas has been growing. In this paper, the vertex-and-edge fault reliability model was investigated and locally optimally mixed reliable networks in the vertex-and-edge fault reliability model were introduced and studied. A reliability comparison criterion was established to determine which one of two given networks with the same vertices and edges was more locally mixed and reliable. Furthermore, locally optimally mixed reliable networks in the graph families $\mathsf{\Omega }(n,n+1)$ and $\mathsf{\Omega }(n,n+2)$ were determined. For application purposes, it is expected to further understand locally optimally mixed reliable networks in other graph families. In this research, the parameters $I_k\left(G\right)$’s were introduced, which have been successfully applied in studies of locally optimally mixed reliable networks in the graph families $\mathsf{\Omega }(n,n+1)$ and $\mathsf{\Omega }(n,n+2)$. Future research can address the investigations of the roles these parameters, $I_k\left(G\right)$’s, will play in studying network reliability, and the determination of locally optimally mixed reliable networks in the graph family $\mathsf{\Omega }(n,n+k)$ when k becomes larger.