The Reliability and Fault Tolerance of Conditional Recursive Networks

Yilin Song, Yinkui Li^*

Department of Mathematics, Qinghai Minzu University, Xining, China.

DOI: 10.4236/jamp.2025.135090                

Abstract

The generalized $k$ -connectivity ${\kappa }_k\left(G\right)$ and $k$ -edge-connectivity ${\lambda }_k\left(G\right)$ of a graph $G$ are a natural generalization of traditional connectivity $\kappa \left(G\right)$ and edge connectivity $\lambda \left(G\right)$ , respectively, which for $\kappa \left(G\right)={\kappa }_2\left(G\right)$ and $\lambda \left(G\right)={\lambda }_2\left(G\right)$ . They are important parameters which can often be used to measure the reliability and fault tolerance of interconnection networks. CRNs is a new family of composite networks based on the complete graph, which contain common networks and have the same structural properties as alternating group network, and may also include some unknown networks. In this paper, we investigate the generalized 3-connectivity and 3-edge-connectivity of CRNs, and show that ${\kappa }_3\left(G_{l,m}\right)={\lambda }_3\left(G_{l,m}\right)=m-2$ .

Keywords

The Generalized -Connectivity, The Generalized -Edge-Connectivity, Conditional Recursive Networks

1. Introduction

Graph packing problem is one of the central problems in graph theory and combinatorial optimization. The Steiner tree packing problem has become a well-established area. For example, a given network $G$ , we choose arbitrary $k$ nodes such that one of them is a broadcaster, and all other nodes are either users or routers (also called switches). The broadcaster wants to broadcast as many streams of movies as possible, so that the users have the maximum number of choices. Each stream of movie is broadcasted via a tree connecting all the users and the broadcaster. Hence we need to find the maximum number Steiner trees connecting all the users and the broadcaster, and it is a Steiner tree packing problem. In 1985, Hager proposed the generalized connectivity of a graph to describe Steiner tree packing problem and investigate the reliability and the fault tolerance of large networks.

For a graph $G=\left(V,E\right)$ with order $n$ and a vertex set $S\subseteq V$ with at least two vertices, an $S$ -Steiner tree or a Steiner tree connecting $S$ (or simply, an $S$ -tree) is a subgraph $T=\left(V^{\prime },E^{\prime }\right)$ of $G$ that is a tree with $S\subseteq V^{\prime }$ . Two Steiner trees $T$ and $T^{\prime }$ connecting $S$ are said to be internally disjoint if $V\left(T\right)\cap V\left(T^{\prime }\right)=S$ and $E\left(T\right)\cap E\left(T^{\prime }\right)=\varnothing$ . The generalized local connectivity$\kappa \left(S\right)$ is the maximum number of internally disjoint $S$ -trees connecting $S$ in $G$ . For an integer $k$ with $2\le k\le n$ , the generalized $k$ -connectivity ${\kappa }_k\left(G\right)$ of $G$ is defined as ${\kappa }_k\left(G\right)=\text{min}\left\{\kappa \left(S\right)|S\subseteq V\left(G\right),\left|S\right|=k\right\}$ and ${\kappa }_2\left(G\right)=\kappa \left(G\right)$ . Correspondingly, for any vertex set $S\subseteq V\left(G\right)$ with $\left|S\right|\ge 2$ , two $S$ -trees $T$ and $T^{\prime }$ connecting $S$ are said to be edge disjoint if $E\left(T\right)\cap E\left(T^{\prime }\right)=\varnothing$ . And the generalized local edge-connectivity $\lambda \left(S\right)$ is the maximum number of edge disjoint $S$ -trees connecting $S$ in $G$ . For an integer $k$ with $2\le k\le n$ , the generalized $k$ -edge-connectivity${\lambda }_k\left(G\right)$ of $G$ is defined as ${\lambda }_k\left(G\right)=\text{min}\left\{\lambda \left(S\right)|S\subseteq V\left(G\right),\left|S\right|=k\right\}$ and ${\lambda }_2\left(G\right)=\lambda \left(G\right)$ . The generalized connectivity has attracted much attention from researchers in the area of graph theory, combinatorial optimization and theoretical computer sciences, and has become a well-established research topic [1]-[5] and a book [6]. As we have known, even for some very special graphs, it is very hard to get the exact values of their generalized $k$ -connectivity for general $k$ . In [7], S. Li determined the generalized 3-connectivity of graphs such as star graphs $S_n$ and bubble-sort graphs $B_n$ . J. Wang [8] considered the generalized 3-connectivity of burnt pancake graphs $B{P}_n$ and godan graphs. S. Zhao [9] determined the generalized 3-connectivity of alternating group graphs and $\left(n,k\right)$ -star graphs.

In this paper, we focus on a new family of networks, called CRNs, which contain common networks and have the same structural properties as alternating group network. This new family of networks is recursive in terms of network structure, that is, $m$ -dimensional CRNs can be decomposed into $m$ node disjoint $m-1$ dimensional CRNs (see Figure 1). We determined the generalized 3-connectivity and the generalized 3-edge-connectivity of CRNs and show that ${\kappa }_3\left(G_{l,m}\right)={\lambda }_3\left(G_{l,m}\right)=m-2$ .

All graphs considered in this paper are undirected, finite and simple. We refer to the book [10] for graph theoretical notation and terminology not described here. For a graph $G$ , we by $V\left(G\right)$ , $E\left(G\right)$ , $\text{Δ}\left(G\right)$ , $\delta \left(G\right)$ , $d_G\left(v\right)$ and $G\left[S\right]$ denote the vertex set, the edge set, the maximum degree, the minimum degree, the degree of vertex $v$ and the subgraph of $G$ induced by $S\subseteq V\left(G\right)$ , respectively. As usual, $E\left(G\left[S\right]\right)$ simplifies as $E\left(S\right)$ and we by $\left[n\right]$ denote the set of positive integers $\left\{1,2,\cdots ,n\right\}$ , by $E\left(S_1,S_2\right)$ denote the set of edge whose one end-vertex is in $S_1$ and another in $S_2$ .

2. Preliminary

We first define a new family of networks, called CRNs, which contain common networks and have the same structural properties as alternating group network.

Definition 1. [11] Let $l\left(\ge 3\right)$ be an integer and $K_l$ be a complete graph. The $l$ -order 1-dimensional conditional recursive networks (simplified CRNs), denoted by $G_{l,1}$ , is isomorphic to $K_l$ . For $m\ge 2$ , the $l$ -order $m$ -dimensional conditional recursive networks $G_{l,m}\cong K_l$ for $1\le m\le l$ and for $m\ge l+1$ , $G_{l,m}$ can be divided into $m$ disjoint subnetworks $G_{l,m-1}^j$ for $j\in \left\{1,2,\cdots ,m\right\}$ , where $G_{l,m-1}^j\cong G_{l,m-1}$ . $G_{l,m}$ usually denoted by $G_{l,m-1}^1\oplus G_{l,m-1}^2\oplus \cdots \oplus G_{l,m-1}^m$ and satisfies the following conditions.

1) For any $1\le i\ne j\le m$ , $\left|E\left(G_{l,m-1}^i,G_{l,m-1}^j\right)\right|=\frac{\left(m-2\right)!}{\left(l-1\right)!}$ .

2) $G_{l,m}$ has a perfect matching $M=E\left(G_{l,m}\right)-E\left({\displaystyle {\cup }_{i=1}^m{G}_{l,m-1}^i}\right)$ .

3) For any vertex $v\in V\left(G_{l,m-1}^i\right)$ , $v$ has only one external neighbor in $G_{l,m}-G_{l,m-1}^i$ .

4) $G_{l,m}$ can be decomposed into $\frac{m!}{r!}$ disjoint subnetworks $G_{l,r}$ when $m\ge l+1$ .

Lemma 2. [11] Let $G_{l,m}$ be $l$ -order $m$ -dimensional CRNs for $m\ge l\ge 3$ . Then

1) $G_{l,m}$ is a $\left(m-1\right)$ -regular graph with $\frac{m!}{\left(l-1\right)!}$ vertices.

2) $\kappa \left(G_{l,m}\right)=m-1$ .

To make it easier for the reader, $G_{3,m}$ for $1\le m\le 5$ illustrated in Figure 1.

Figure 1. The CRNs $G_{3,m}$ for $m\in \left\{1,2,3,4,5\right\}$ .

Lemma 3. [10] Let $G$ be a $k$ -connected graph, let $x$ be a vertex of $G$ and let $Y\subseteq V\left(G\right)\backslash \left\{x\right\}$ be a set of at least $k$ vertices of $G$ . Then there exists a $k$ -fan in $G$ from $x$ to $Y$ , that is, there exists a family of $k$ internally disjoint $\left(x,Y\right)$ -paths whose terminal vertices are distinct in $Y$ .

Lemma 4. [10] Let $G$ be a $k$ -connected graph, and let $X,Y\subseteq V\left(G\right)$ with $\left|X\right|,\left|Y\right|\ge k$ . Then there exists a set of $k$ pairwise vertex disjoint $\left(X,Y\right)$ -paths in $G$ .

Lemma 5. [12] For every two integers $n$ and $k$ with $2\le k\le n$ , ${\kappa }_k\left(K_n\right)=n-\lceil \frac{k}{2}\rceil$ .

Observation 6. Let $n,k$ be two integers with $2\le k\le n$ . If $G$ is a connected graph of order $n$ , then ${\kappa }_k\left(G\right)\le {\lambda }_k\left(G\right)\le \delta \left(G\right)$ .

Lemma 7. [6] Let $G$ be a connected graph of order $n$ with minimum degree $\delta$ . If there are two adjacent vertices of degree $\delta$ , then ${\kappa }_k\left(G\right)\le {\lambda }_k\left(G\right)\le \delta -1$ for $3\le k\le n$ . Moreover, the upper bound is sharp.

Lemma 8. [13] Let $G$ be a connected graph with $n$ vertices. For every two integers $k$ and $r$ with $k\ge 0$ and $r\in \left\{0,1,2,3\right\}$ , if $\kappa \left(G\right)=4k+r$ , then

${\kappa }_3\left(G\right)\ge 3k+\lceil \frac{r}{2}\rceil$ . Moreover, the lower bound is sharp.

3. Main Results

In this section, we determine the generalized 3-connectivity and 3-edge-connectivity of conditional recursive network CRNs $G_{l,m}$ .

Theorem 9. Let $m$ be integer and $G_{l,m}$ be $l$ -order $m$ -dimensional CRNs. Then

${\kappa }_3\left(G_{l,m}\right)=\{\begin{array}{ll}l-2,\hfill & \text{if}1\le m\le l;\hfill \\ m-2,\hfill & \text{if}m\ge l+1.\hfill \end{array}$

Proof. Clearly, $G_{l,m}\cong K_l$ for $1\le m\le l$ , by lemma 5 we directly get

${\kappa }_3\left(G_{l,m}\right)={\kappa }_3\left(K_l\right)=l-\lceil \frac{3}{2}\rceil =l-2$ . Now consider the case for $m\ge l+1$ , since

$G_{l,m}$ is $\left(m-1\right)$ -regular, by lemma 7, we have ${\kappa }_3\left(G_{l,m}\right)\le \delta -1=m-2$ . Next, we show ${\kappa }_3\left(G_{l,m}\right)\ge m-2$ . This suffice to prove that there exist at least $m-2$ internally disjoint $S$ -trees in $G_{l,m}$ for any 3-element set $S\subseteq V\left(G_{l,m}\right)$ . For convenience narration, denote $G_{l,m}=G^1\oplus G^2\oplus \cdots \oplus G^m$ , where $G^i\cong G_{l,m-1}$ for $i\in \left[m\right]$ and suppose $S=\left\{x,y,z\right\}\subseteq V\left(G_{l,m}\right)$ .

Case 1 $\left|S\cap V\left(G^i\right)\right|=3$ for some $i\in \left[m\right]$ .

Without loss of generality, suppose $x,y,z\in V\left(G^1\right)$ . We proceed by induction on $m$ . First, by lemma 8, we get ${\kappa }_3\left(G_{l,3}\right)\ge \lceil \frac{2}{2}\rceil =1$ , the conclusion holds for

$m=3$ . Assume that the conclusion holds for $m=k\left(\ge 4\right)$ , this means that ${\kappa }_3\left(G_{l,k}\right)\ge k-2$ for $k\ge l+1$ . Now we consider $m=k+1$ . Notice $G_{l,k+1}=G^1\oplus G^2\oplus \cdots \oplus G^k$ with $G^i\cong G_{l,k}$ for $i\in \left[k\right]$ and $x,y,z\in V\left(G^1\right)$ , by hypothesis, we have ${\kappa }_3\left(G^1\right)={\kappa }_3\left(G_{l,k}\right)\ge k-2$ . This implies that there are at least $k-2$ internally disjoint $S$ -trees in $G^1$ , named $T_1,T_2,\cdots ,T_{k-2}$ . By the Definition 2(3), each of $x,y,z$ has only one external neighbor in $G_{l,k+1}-G^1$ and we can use the external neighbors construct a new $S$ -tree in $G_{l,k+1}$ , named $T_{k-1}$ . Total up all, we get at least $k-1$ internally disjoint $S$ -trees $T_1,T_2,\cdots ,T_{k-1}$ in $G_{l,k+1}$ . The conclusion holds for $m=k+1\left(k\ge 4\right)$ . By the above argument, we get ${\kappa }_3\left(G_{l,m}\right)\ge m-2$ for $m\ge l+1$ .

Case 2 $\left|S\cap V\left(G^i\right)\right|=2$ and $\left|S\cap V\left(G^j\right)\right|=1$ for distinct $i,j\in \left[m\right]$ .

Without loss of generality, suppose $x,y\in V\left(G^1\right)$ and $z\in V\left(G^2\right)$ . By $\kappa \left(G^1\right)=m-2$ , we know that $G^1$ contains at least $m-2$ internally disjoint $\left(x,y\right)$ -paths in $G^1$ , named $P_i$ for $i\in \left[m-2\right]$ . Consider $z\in V\left(G^2\right)$ and $\kappa \left(G^2\right)=m-2$ , there exist a $\left(m-2\right)$ -fan in $G^2$ from $z$ to $Z=\left\{z_1,z_2,\cdots ,z_{m-2}\right\}\subseteq V\left(G^2\right)\backslash \left\{z\right\}$ , they are internally disjoint $\left(z,Z\right)$ paths, denoted as $L_i$ for $i\in \left[m-2\right]$ . Now select $x_i\in V\left(P_i\right)$ and ${z^{\prime }}_i\in V\left(L_i\right)$ , suppose ${x^{\prime }}_i$ is the external neighbor of $x_i$ in $G_{l,k+1}-G^1$ . Let $X^{\prime }=\left\{{x^{\prime }}_1,{x^{\prime }}_2,\cdots ,{x^{\prime }}_{m-2}\right\}$ , $Z^{\prime }=\left\{{z^{\prime }}_1,{z^{\prime }}_2,\cdots ,{z^{\prime }}_{m-2}\right\}$ . By lemma 4, there exist a set of $m-2$ pairwise vertex disjoint $\left(X^{\prime },Z^{\prime }\right)$ -paths in $G$ , named ${x^{\prime }}_i{Q}_i{z^{\prime }}_i$ for $i\in \left[m-2\right]$ . Then we construct $T_i=P_i\cup x_i{x^{\prime }}_i+{x^{\prime }}_i{Q}_i{z^{\prime }}_i\cup {z^{\prime }}_i{L}_{i}z$ for $i\in \left[m-2\right]$ and obtain $m-2$ internally disjoint $S$ -trees in $G_{l,m}$ (See Figure 2). Thus we have ${\kappa }_3\left(G_{l,m}\right)\ge m-2$ .

Figure 2. Illustration for Case 2.

Case 3 $\left|S\cap V\left(G^i\right)|=|S\cap V\left(G^j\right)|=|S\cap V\left(G^k\right)\right|=1$ for distinct $i,j,k\in \left[m\right]$

Without loss of generality, suppose $x\in V\left(G^1\right),y\in V\left(G^2\right)$ and $z\in V\left(G^3\right)$ . Notice that $G^1,G^2$ and $G^3$ are $\left(m-2\right)$ -connected, there exist a $\left(m-2\right)$ -fan in $G^1$ from $x$ to $X=\left\{x_1,x_2,\cdots ,x_{m-2}\right\}\subseteq V\left(G^1\right)\backslash \left\{x\right\}$ , a $\left(m-2\right)$ -fan in $G^2$ from $y$ to $Y=\left\{y_1,y_2,\cdots ,y_{m-2}\right\}\subseteq V\left(G^2\right)\backslash \left\{y\right\}$ and a $\left(m-2\right)$ -fan in $G^3$ from $z$ to $Z=\left\{z_1,z_2,\cdots ,z_{m-2}\right\}\subseteq V\left(G^3\right)\backslash \left\{z\right\}$ . Suppose internally disjoint $\left(x,X\right)$ paths are $P_i$ , internally disjoint $\left(y,Y\right)$ paths are $Q_i$ and internally disjoint $\left(z,Z\right)$ paths are $R_i$ for $i\in \left[m-2\right]$ . Now select ${x^{\prime }}_i\in P_i$ , ${y^{\prime }}_i\in Q_i$ and ${z^{\prime }}_i\in R_i$ for $i\in \left[m-2\right]$ and suppose ${\stackrel{⌣}{x}}_i$ and ${\stackrel{⌢}{x}}_i$ respectively are the external neighbor and internal neighbor of ${x^{\prime }}_i$ in $G^1$ . Let $X^{\prime }=\left\{{x^{\prime }}_1,{x^{\prime }}_2,\cdots ,{x^{\prime }}_{m-2}\right\}$ , $\stackrel{⌢}{X}=\left\{{\stackrel{⌢}{x}}_1,{\stackrel{⌢}{x}}_2,\cdots ,{\stackrel{⌢}{x}}_{m-2}\right\}\subseteq V\left(G^1\right)$ , $\stackrel{⌣}{X}=\left\{{\stackrel{⌣}{x}}_1,{\stackrel{⌣}{x}}_2,\cdots ,{\stackrel{⌣}{x}}_{m-2}\right\}\subseteq V\left(G\backslash G^1\right)$ , $Y^{\prime }=\left\{{y^{\prime }}_1,{y^{\prime }}_2,\cdots ,{y^{\prime }}_{m-2}\right\}\subseteq V\left(G^2\right)$ , $Z^{\prime }=\left\{{z^{\prime }}_1,{z^{\prime }}_2,\cdots ,{z^{\prime }}_{m-2}\right\}\subseteq V\left(G^3\right)$ .

By lemma 4, there are $m-2$ pairwise vertex disjoint $\left(\widehat{X},Y^{\prime }\right)$ -paths, named $L_i$ and $m-2$ pairwise vertex disjoint $\left(\stackrel{⌣}{X},Z^{\prime }\right)$ -paths, named $M_i$ for $i\in \left[m-2\right]$ . Based on these analysis, we can construct $m-2$ internally disjoint $S$ -trees $T_i=x{x^{\prime }}_i{\stackrel{⌣}{x}}_i{M}_i{z^{\prime }}_{i}z\cup {x^{\prime }}_i{\stackrel{⌢}{x}}_i{L}_i{y^{\prime }}_{i}y$ for $i\in \left[m-2\right]$ in $G$ (See Figure 3). Thus, we get ${\kappa }_3\left(G_{l,m}\right)\ge m-2$ .

Clearly, $T_1,T_2,\cdots ,T_{m-2}$ are $m-2$ internally disjoint $S$ -trees in $G_{l,m}$ . This follows that ${\kappa }_3\left(G_{l,m}\right)\ge m-2$ .

Figure 3. Illustration for Case 3.

Therefore, ${\kappa }_3\left(G_{l,m}\right)=m-2$ for $m\ge l\ge 3$ . This completes the proof. □

By lemma 7 and Theorem 3.1, we directly get the generalized 3-edge-connectivity of CRNs.

Corollary 1. Let $m$ be integer and $G_{l,m}$ be $l$ -order $m$ -dimensional CRNs. Then

${\lambda }_3\left(G_{l,m}\right)=\{\begin{array}{ll}l-2,\hfill & \text{if}1\le m\le l;\hfill \\ m-2,\hfill & \text{if}m\ge l+1.\hfill \end{array}$

4. Conclusion

The generalized $k$ -connectivity is a natural generalization of the traditional connectivity. It can measure the reliability and fault tolerance of interconnection networks $G$ to connect any $k$ vertices in $G$ . In this paper, we investigate the generalized 3-connectivity of $G_{l,m}$ , and show that ${\kappa }_3\left(G_{l,m}\right)={\lambda }_3\left(G_{l,m}\right)=m-2$ . This result not only enhances the theoretical system for CRN network reliability, but also provides a theoretical foundation for optimizing fault tolerance mechanisms in practical network design. Next, we will study the generalized $k$ -connectivity of $G_{l,m}$ for $k\ge 4$ .

Acknowledgements

The authors would like to thank anonymous reviewers for their valuable comments and suggestions to improve the quality of the article. This work is supported by the Innovation Projects of Qinghai Minzu University (No. 07M2024008) and AFSFQH (No. 2022-ZJ-753).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Gu, R., Li, X. and Shi, Y. (2014) The Generalized 3-Connectivity of Random Graphs. Acta Mathematica Sinica, Chinese Series, 57, 321-330.
[2]	Hager, M. (1985) Pendant Tree-Connectivity. Journal of Combinatorial Theory, Series B, 38, 179-189. https://doi.org/10.1016/0095-8956(85)90083-8
[3]	Kriesell, M. (2009) Edge Disjoint Steiner Trees in Graphs without Large Bridges. Journal of Graph Theory, 62, 188-198. https://doi.org/10.1002/jgt.20389
[4]	Li, X., Mao, Y. and Sun, Y. (2014) On the Generalized (Edge-)connectivity of Graphs. The Australasian Journal of Combinatorics, 58, 304-319.
[5]	Li, Y. and Wei, L. (2023) Note for the Conjecture on the Generalized 4-Connectivity of Total Graphs of the Complete Bipartite Graph. Applied Mathematics and Computation, 458, Article ID: 128225. https://doi.org/10.1016/j.amc.2023.128225
[6]	Li, X. and Mao, Y. (2015) Nordhaus-Gaddum-Type Results for the Generalized Edge-Connectivity of Graphs. Discrete Applied Mathematics, 185, 102-112. https://doi.org/10.1016/j.dam.2014.12.009
[7]	Li, S., Tu, J. and Yu, C. (2016) The Generalized 3-Connectivity of Star Graphs and Bubble-Sort Graphs. Applied Mathematics and Computation, 274, 41-46. https://doi.org/10.1016/j.amc.2015.11.016
[8]	Wang, J., Zhang, Z. and Huang, Y. (2023) The Generalized 3-Connectivity of Burnt Pancake Graphs and Godan Graphs. AKCE International Journal of Graphs and Combinatorics, 20, 98-103. https://doi.org/10.1080/09728600.2023.2212293
[9]	Zhao, S. and Hao, R. (2018) The Generalized Connectivity of Alternating Group Graphs and-Star Graphs. Discrete Applied Mathematics, 251, 310-321. https://doi.org/10.1016/j.dam.2018.05.059
[10]	Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory, GTM 244. Springer.
[11]	Zhang, H., Bian, H. and Meng, J. (2025) Reliability Evaluation of Conditional Recursive Networks under H-Conditional Restriction. Applied Mathematics and Computation, 500, Article ID: 129399. https://doi.org/10.1016/j.amc.2025.129399
[12]	Chartrand, G., Okamoto, F. and Zhang, P. (2009) Rainbow Trees in Graphs and Generalized Connectivity. Networks, 55, 360-367. https://doi.org/10.1002/net.20339
[13]	Li, S., Li, X. and Zhou, W. (2010) Sharp Bounds for the Generalized Connectivity . Discrete Mathematics, 310, 2147-2163.