Abstract
High-performance computing relies heavily on parallel and distributed systems, which promptes us to establish both qualitative and quantitative criteria to assess the fault tolerability and vulnerability of the system’s underlying interconnection networks. Consider the scenario in which large-scale link failures split the interconnection network into several components and each processor has multiple good neighboring processors. In this scenario, the fault tolerability of the system can be measured by g-good-neighbor r-component edge-connectivity, denoted by \(\lambda _{g,r}(G)\), which is defined as the minimum number of edges whose removal results in a disconnected network with at least r connected components and each vertex has at least g good neighbors. It combines the strategies of g-good-neighbor edge-connectivity and component edge-connectivity. In this paper, the g-good-neighbor \((r+1)\)-component edge-connectivity of 3-ary n-cube is investigated. This work is the first attempt enhancing link fault tolerability for 3-ary n-cube under double constraints in the presence of the large-scale faulty links, which breaks down the inherent idea that poses one limitation on the resulting network. In addition, our results cover the work of Xu et al. (IEEE Trans Reliab, 71(3):1230–1240, 2022) and Li et al. (J Parallel Distrib Comput, 27:104886, 2024). Finally, the compared results reveal that the g-good-neighbor \((r+1)\)-component edge-connectivity is almost r times the size of g-good-neighbor edge-connectivity and much larger than \((r+1)\)-component edge-connectivity in 3-ary n-cube.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Massively parallel computing systems employing hundreds to thousands of processors are commercially available today and offer substantially higher raw computing power than the fastest sequential supercomputers. Availability of such systems has fueled interest in investigating the performance of parallel and distributed systems containing a large number of processors. Parallel computing architectures for large-scale parallel and distributed systems have advanced significantly during the last decades. The interconnection network is well recognized to be critical in large-scale parallel and distributed systems, since its design has a direct impact on the system’s performance and cost-effectiveness [3]. Topological structure is generally deemed a key design concern for interconnection networks. A large number of topological structures have been proposed and explored, most notably the hypercube structure and its variants, such as k-ary n-cube, folded hypercube, crossed cube, and so on. The k-ary n-cube, especially the 3-ary n-cube, has attracted a great deal of interest due to its many appealing attributes [11], including its capacity to minimize message latency and ease of implementation. A variety of parallel and distributed systems, including the J-machine [18], the Cray T3D [12], the Cray T3E [2], and the IBM supercomputer BlueGene/L [1], have been constructed with the k-ary n-cube as the underlying topological structure. The IBM supercomputer BlueGene/L’s fundamental architecture is the 3-ary n-cube.
With the increasing of network scale and business traffic, interconnection network is facing a lot of challenges, among which fault tolerability is of the most importance. Actually, the network malfunction, especially for link failure, is common and always inevitable. In a large-scale parallel and distributed system, the link failure on the data plane occurs more occasionally and frequently, and some links are likely to fail every half hour on average [9]. Link failure results in the interruption of traffic transmission and further degrades the network performance. Therefore, considering the seriousness and inevitability of link failure, both academia and industry pay great attention to the link fault tolerability.
There are several metrics that characterize the link fault tolerability of interconnection networks, such as classical edge-connectivity, extra edge-connectivity, component edge-connectivity, g-good-neighbor edge-connectivity, cycle edge-connectivity, embedded edge-connectivity, and so on. Among these metrics, extra edge-connectivity, component edge-connectivity and g-good-neighbor edge-connectivity of many prominent networks have been widely investigated over the years. The h-extra edge-connectivity \(\lambda _h(G)\) was proposed by Fàbrega et al. [8], which is defined as the minimum number of edges whose removal results in a disconnected network and each component has at least \(h+1\) vertices. Many scholars have studied its h-extra edge-connectivity in diverse networks, such as bijective connection networks \(B_n\) [28], folded hypercube \(FQ_n\) [29], augmented cube \(AQ_n\) [23, 31], 3-ary n-cube \(Q_n^3\) [22], folded crossed cube \(FCQ_n\) [19]. The g-good-neighbor edge-connectivity \(\lambda ^g(G)\) was proposed by Latifi [13], which is defined as the minimum number of edges whose removal results in a disconnected network and each vertex has at least g neighbors. The g-good-neighbor edge-connectivities of many networks, such as bijective connection networks \(B_n\) [14], modified bubble-sort networks \(MB_n\) [5], augmented cube \(AQ_n\) [30], k-ary n-cube [15], have been determined. By the minimality of edge-cuts, the two types of conditional edge-connectivities mentioned above allow only two components to be generated after deleting the smallest conditional edge-cut. Generally speaking, a disconnected network with two components may not be as bad as a disconnected network with many more components. By constraining the number of components of the disconnected network, the r-component edge-connectivity \(c\lambda _r(G)\) was proposed by Sampathkumar [20], which is defined as the minimum number of edges whose removal results in a disconnected network with at least r connected components. A lot of related work on specific networks have been studied, including hypercube \(Q_n\) [33], locally twisted cube \(LTQ_n\) [21], augmented cube \(AQ_n\) [31], bijective connection networks \(B_n\) [16], 3-ary n-cube \(Q_n^3\) [22], hamming graph \(K_L^n\) [25], folded Petersen networks \(P^n\) [24]. Note that this metric only puts a limit on the number of components but not on the structure of each component, i.e., it may produce sub-networks that have only one vertex, but for which it is not able to perform any of the tasks assigned by the system.
As a result, in order to establish a balance between the number of components and their structure, Yang et al. [26] and Liu et al. [17] proposed two new concepts, namely h-extra r-component edge-connectivity and g-good-neighbor r-component edge-connectivity, by integrating the strategies of r-component edge-connectivity and one of h-extra edge-connectivity and g-good-neighbor edge-connectivity, respectively. Both emphasize the double constraints on the resulting network after removing the smallest edge-cut. The h-extra r-component edge-connectivity, denoted by \(c\lambda _r^h(G)\), is defined as the minimum number of edges whose removal results in a disconnected network with at least r connected components and each component has at least \(h+1\) vertices. The g-good-neighbor r-component edge-connectivity, denoted by \(\lambda _{g,r}(G)\), is defined as the minimum number of edges whose removal results in a disconnected network with at least r connected components and each vertex has at least g neighbors. In particular, \(c\lambda _r^0(G)\) and \(\lambda _{0,r}(G)\) reduce to r-component edge-connectivity \(c\lambda _r(G)\), while \(c\lambda _2^h(G)\) and \(\lambda _{g,2}(G)\) degrade into h-extra edge-connectivity \(\lambda _h(G)\) and g-good-neighbor edge-connectivity \(\lambda ^g(G)\), respectively. As applications, Yang et al. [26] explored the h-extra 3-component edge-connectivities of bijective connection networks \(B_n\) and folded hypercube \(FQ_n\) for specific ranges of h. Moreover, Liu et al. [17] investigated the g-good-neighbor r-component edge-connectivity of hypercube in the same specific ranges with regarded to g and r. For all the related work mentioned above, we present all the results in Table 1 to facilitate the knowledge of the progress of the related work.
In this paper, we focus on the g-good-neighbor \((r+1)\)-component edge-connectivity of 3-ary n-cube. More specifically, we obtain \(\lambda _{g, r+1}(Q_n^3)=(2-d)(2n-g)r\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }-[\frac{1}{2}ex_{(2-d)r}(Q_n^3)-(1-d)r]\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\) for \(n\ge 3\), \(1\le (2-d)r\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\le (2-c)\cdot 3^{\big \lceil \frac{n}{2}\big \rceil -1}\) or \(r=3^{k_0}, 0\le k_0\le \left\lfloor \frac{n}{2}\right\rfloor -1\) and \(0\le g\le 2(n-2k_0-1)\), where \(d~\equiv g \pmod {2}\), \(ex_{(2-d)r}(Q_n^3)\) represents the maximum degree sum of the subgraph induced by \((2-d)r\) vertices of \(Q_n^3\) whose exact value is determined by Xu et al. [22].
The rest of this paper is organized as follows. Section 2 reviews some notations and the structure and properties of the 3-ary n-cube. Section 3 constructs a g-good-neighbor \((r+1)\)-component edge-cut. Section 4 determines g-good-neighbor \((r+1)\)-component edge-connectivity of 3-ary n-cube. Section 5 presents some examples. Section 6 concludes the work.
2 Preliminaries
First of all, we assume that all parameters are nonnegative integers. Let G(V(G), E(G)) be a network or graph, where |V(G)|, |E(G)| denote the order and size of G, respectively. For \(W \subseteq V(G) (\text {resp}., E(G))\), G[W] denotes the subgraph of G induced by W, and \(G-W\) denotes the subgraph of G induced by \(V(G)\setminus W\) (resp., \(E(G)\setminus W\)). For vertex subsets \(T_1, T_2,\ldots , T_r\subset V(G)\), we denote by \(E(T_1,T_2,\ldots , T_r)\) the edge set of G with one vertex in \(T_i\), and the other in \(T_j\), where \(T_i\cap T_j =\varnothing , 1\le i<j \le r\). The degree of a vertex v, denoted by \(d_G(v)\), is the number of vertices incident to v. We denote by \(\delta (G)\) the minimum degree of graph G. A graph G is k-regular if \(d_G(v)=k\) for any vertex \(v\in V(G)\). The component of G is the maximal connected subgraph of G. The graph \(G_1\) is isomorphic to \(G_2\) which is indicated by the notation \(G_1 \cong G_2\). Let \(S_r\) be the set \(\{0, 1, 2, \ldots , r-1\}\), \(L_l^n\) be the set \(\{t_i^n\}_{i=0}^{l-1}\), where \(t_i^n\) is the n-ternary string conversed by the decimal number i. Let D(u, v) be the number of different positions in the n-ternary strings u and v. For graph definitions and notations not defined here, we follow [4].
The definition of 3-ary n-cube is recalled as follows.
Definition 1
[10] The 3-ary n-cube, denoted by \(Q_n^3\), has \(3^n\) vertices, where each vertex has form \(\{z_nz_{n-1} \ldots z_1 ~|~ z_i\in S_3, 1\le i\le n\}\). For any two vertices u, v, \((u,v)\in E(Q_n^3)\) if and only if \(D(u,v)=1\).
The 3-ary n-cube \(Q_n^3\) is a 2n-regular 2n-connected graph [6]. \(Q_n^3\) can be decomposed into three vertex and edge-disjoint 3-ary \((n-1)\)-cubes, denoted by \(Q_n^3[0]\), \(Q_n^3[1]\), and \(Q_n^3[2]\), which are induced by the vertices of \(Q_n^3\) with the ith coordinate 0, 1, and 2, respectively. Clearly, \(Q_n^3[i]\) and \(Q_n^3[j]\) are joined by one perfect matching, so \(|E(V(Q_n^3[i]),V(Q_n^3[j]))|=3^{n-1}\) for \(i\ne j\in S_3\). For convenience, we denote \(Q_n^3\) as \(Q_n^3[0]\bigoplus Q_n^3[1]\bigoplus Q_n^3[2]\). We denote by \(t_l^{n-m}Z^m\) the vertex set
where \(x_nx_{n-1}\ldots x_{m+1}\) is \((n-m)\)-ternary string conversed by the decimal number l, Z represents variable in \(S_3\). By the definition of the \(Q_n^3\), the subgraph \(Q_n^3[t_l^{n-m}Z^m]\cong Q_m^3\). The 3-ary 3-cube \(Q_3^3\) is illustrated in Fig. 1.
Denote by \(\frac{ex_l(Q_n^3)}{2}\) the maximum size (the number of edges) of the subgraph induced by a vertex set with a given size l in \(Q_n^3\), where \(ex_l(Q_n^3)\) represents the maximum degree sum of the subgraph induced by l vertices of \(Q_n^3\), i.e.,
Fan et al. [7] showed that \(\frac{ex_l(Q_n^3)}{2}\) can be achieved by the induced subgraph \(Q_n^3[L_l^n]\), i.e., \(E(Q_n^3[L_l^n])=\frac{ex_l(Q_n^3)}{2}\). Whereafter, Zhang et al. [32] characterized structural features of subgraph \(Q_n^3[L_l^n]\) in accordance with the ternary decomposition of l. Let \(l =\sum _{i=0}^{s} a_i3^{k_i}\) be the ternary decomposition of l such that \(k_0 = [\log _3 l]\), \(a_0 = [l-2\cdot 3^{k_0}]^++1\) and \(k_i=[\log _3(l -\sum _{j=0}^{i-1} a_j3^{k_j})]\), \(a_i=[l-\sum _{j=0}^{i-1} a_j3^{k_j}- 2\cdot 3^{k_i}]^++1\) for \(1\le i\le s\), where
In [32], \(L_l^n\) can be expressed as \(V(Q^0\cup Q^1\cup \cdots \cup Q^s)\), where each \(Q^i\) is a subgraph induced by vertex set with \(a_i3^{k_i}\) vertices, that is, each \(Q^i\) is either 3-ary \(k_i\)-subcube or disjoint union of two 3-ary \(k_i\)-subcubes connected by a perfect matching. In particular, the single vertex is deemed to 3-ary 0-subcube. In addition, \(Q^i\) is taken from a 3-ary n-cube which is obtained from \(Q^{i-1}\) by changing the 0 of \((t_i+1)th\) coordinate of \(Q^{i-1}\) to 1 or the 0 and 1 of \((t_i+1)th\) coordinate of \(Q^{i-1}\) to 2 for \(1\le i\le s\). So there exists at least one edge between the vertices in different \(Q^i\)s. We present some examples in the Table 2 to illustrate this structure.
Motivated by the idea of Fan et al. [7], Xu et al. [22] determined the exact expression of \(ex_l(Q_n^3)\) as follows.
Lemma 1
[22] Let \(1\le l\le 3^n\) and \(l=\sum _{i=0}^s a_i3^{k_i}\) be the ternary decomposition of l. Then, we have \(\frac{1}{2}ex_l(Q_n^3)=|E(Q_n^3[L_l^n])|=\sum _{i=0}^s(a_ik_i+a_i-1)3^{k_i}+\sum _{i=1}^s\left( \sum _{j=0}^{i-1}a_j\right) a_i3^{k_i}.\)
3 Construction of g-good-neighbor \((r+1)\)-component edge-cut
In this section, we will construct a g-good-neighbor \((r+1)\)-component edge-cut in the 3-ary n-cube.
Lemma 2
[32] For two positive integers n, l, let \(\overline{L_l^n}=V(Q_n^3)\setminus L_l^n\). Both \(Q_n^3[L_l^n]\) and \(Q_n^3[\overline{L_l^n}]\) are connected.
3.1 \(g=0 \pmod {2}\)
First of all, we define some notations. Let n, g, r be three integers such that \((r+1)\cdot 3^{\frac{g}{2}}\le 3^n\). For any \(i\in S_r\), let \(T_i=t_i^{n-\frac{g}{2}}Z^{\frac{g}{2}}\) and \(G_i=Q_n^3[T_i]\). Let \(T_r=V(Q_n^3)-\bigcup _{i\in S_r}T_i\) and \(G_r=Q_n^3[T_r]\). Obviously, \(G_i\cong Q_{\frac{g}{2}}^3\) for any \(i\in S_r\) and \(T_i\cap T_j=\varnothing\) for \(i\ne j \in S_r\). We contract each \(T_i\) into a vertex \(t_i\) for \(i\in S_r\) and delete the multiple edges between \(T_i\) and \(T_j\) when \(E(T_i, T_j)\ne \varnothing\) for \(i\ne j \in S_r\). Then the graph \(G^*\) induced by \(\{t_0, t_1, \ldots , t_{r-1}\}\) is isomorphic to \(Q_n^3[L_r^n]\). Note that \((t_i,t_j)\in E(G^*)\) if and only if \(|E(T_i, T_j)|=3^{\frac{g}{2}}\), hence, \(|E(T_0, T_1, \ldots , T_{r-1})|=|E(G^*)|\cdot 3^{\frac{g}{2}}=\frac{1}{2}ex_r(Q_n^3)\cdot 3^{\frac{g}{2}}\).
Lemma 3
If \(g=0 \pmod {2}\), then
Proof
Let \(T_i\) be defined as above for \(i\in S_r\). In light of definition of \(T_i\), we have \(\bigcup _{i\in S_r}T_i=L_{r\cdot 3^{\frac{g}{2}}}^n\). By Lemma 1, \(2|E(Q_n^3[\bigcup _{i\in S_r}T_i])|=ex_{r\cdot 3^{\frac{g}{2}}}(Q_n^3)\). Therefore,
\(\square\)
Lemma 4
For any \(i\in S_{r+1}\), the subgraph \(G_i\) is connected and \(\delta (G_i)\ge g\).
Proof
For any \(i\in S_r\), \(G_i\cong Q_{\frac{g}{2}}^3\), thereby, \(G_i\) is connected and \(\delta (G_i)\ge g\). In light of definition of \(T_i\), we have \(\bigcup _{i\in S_r}T_i=L_{r\cdot 3^{\frac{g}{2}}}^n\) and \(T_r=\overline{L_{r\cdot 3^{\frac{g}{2}}}^n}\). By Lemma 2, \(G_r\) is connected. Let \(r=\sum _{j=0}^{s}a_j3^{k_j}\) be the ternary decomposition of r, \(k_j+\frac{g}{2}=l_j\). Then,
where \(n-1-h=l_s, b_h=3-a_s\) and
for \(0\le i\le h-1\). According to the above expression of \(r'\), \(b_i=0\) for some i’s. Therefore, \(r'\) can be rephrased as \(r'=\sum _{i=0}^{h'}b_i'3^{q_i}\), where \(q_0>q_1>\ldots >q_{h'}=l_s\) and \(b_{h'}'=3-a_s\). According to the construction of \(G_r\), each vertex in \(G_r\) falls in some \(Q_{q_i}^3\). In view of \(q_i\ge l_s=k_s+\frac{g}{2}\) for any \(i\in S_{h'+1}\), \(\delta (G_r)\ge g\). \(\square\)
Lemma 5
Let n, g, r be three integers such that \((r+1)\cdot 3^{\frac{g}{2}}\le 3^n\), where \(g=0 \pmod {2}\). Then
Proof
We prove this lemma by constructing a g-good-neighbor \((r+1)\)-component edge-cut with size \((2n-g)r\cdot 3^{\frac{g}{2}}-\frac{1}{2}ex_r(Q_n^3)\cdot 3^{\frac{g}{2}}\). Suppose that \(G_i\) and \(T_i\) for any \(i\in S_{r+1}\) are defined as above. Then, by Lemma 4, \(Q_n^3-E(T_0, T_1, \ldots , T_r)\) is disconnected and has exactly \(r+1\) components \(G_0, G_1, \ldots , G_r\) and \(\delta (G_i)\ge g\) for any \(i\in S_{r+1}\). Moreover, \(|E(T_0, T_1, \ldots , T_{r-1})|=|E(G^*)|\cdot 3^{\frac{g}{2}}=\frac{1}{2}ex_r(Q_n^3)\cdot 3^{\frac{g}{2}}\). Therefore, we have
Thus, the edge set \(E(T_0, T_1, \ldots , T_r)\) is a g-good-neighbor \((r+1)\)-component edge-cut with size \((2n-g)r\cdot 3^{\frac{g}{2}}-\frac{1}{2}ex_r(Q_n^3)\cdot 3^{\frac{g}{2}}\). By the definition of \(\lambda _{g, r+1}(Q_n^3)\), we have \(\lambda _{g, r+1}(Q_n^3)\le (2n-g)r\cdot 3^{\frac{g}{2}}-\frac{1}{2}ex_r(Q_n^3)\cdot 3^{\frac{g}{2}}.\) \(\square\)
3.2 \(g=1 \pmod {2}\)
Similarly, we define some notations. Let n, g, r be three integers such that \(2(r+1)\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\le 3^n\). For any \(i\in S_{2r}\), let \(T_i=t_i^{n-\left\lfloor \frac{g}{2}\right\rfloor }Z^{\left\lfloor \frac{g}{2}\right\rfloor }\). Obviously, \(T_i\cap T_j=\varnothing\) for \(i\ne j \in S_{2r}\). We contract each \(T_i\) into a vertex \(t_i\) for \(i\in S_{2r}\) and delete the multiple edges between \(T_i\) and \(T_j\) when \(E(T_i, T_j)\ne \varnothing\) for \(i\ne j \in S_{2r}\). Then the graph \(G^*\) induced by \(\{t_0, t_1, \ldots , t_{2r-1}\}\) is isomorphic to \(Q_n^3[L_{2r}^n]\). Note that \((t_i,t_j)\in E(G^*)\) if and only if \(|E(T_i, T_j)|=3^{\left\lfloor \frac{g}{2}\right\rfloor }\), so a perfect matching in \(Q_n^3[L_{2r}^n]\) corresponds to a paired-partitiom of \(\{T_0, T_1, \ldots , T_{2r-1}\}\) such that each pairwise paired induced subgraph is isomorphic to \(Q_{\left\lfloor \frac{g}{2}\right\rfloor +1}^3[0]\oplus Q_{\left\lfloor \frac{g}{2}\right\rfloor +1}^3[1]\).
Theorem 1
Algorithm 1 outputs one perfect matching M in \(Q_n^3[L_{2r}^n]\).
Proof
By Algorithm 1, it is easy to see that M covers all vertices in \(L_{2r}^n\). Next, it suffices to show that for each \((x,y)\in M\), \((x,y)\in E(Q_n^3[L_{2r}^n])\). Obviously, \(D(t_0^n, t_1^n)=1\) and \(D(t_0^n, t_{3^a}^n)=1\). By the definitions of \(Q_n^3\) and \(t_j^n\), if \(r=1\), then \((t_0^n, t_1^n)\in E(Q_n^3[L_{2r}^n])\), while if \(r>1\), \((t_0^n, t_{3^a}^n)\in E(Q_n^3[L_{2r}^n])\). According to the lines 7 to 13 in Algorithm 1 and choice of w, if \(l=k_s\), then \(a_s\ne 2\). Thus, \(D(t_w^n, t_{w+3^l}^n)=1\), which implies that \((t_w^n, t_{w+3^l}^n)\in E(Q_n^3[L_{2r}^n])\). \(\square\)
For example, let \(n=3\) and \(r=8\), then by Algorithm 1, we can find one perfect matchinig in \(Q_3^3[L_{16}^3]\), that is \(\{(000,100), (001,002), (010,020), (011,012), (021,022), (101,102), (110,120), (111,112)\}\) (see Fig. 2).
By Theorem 1, there are r pairs of subgraphs \(G_0, G_1, \ldots , G_{r-1}\) such that \(G_j \cong Q_{\left\lfloor \frac{g}{2}\right\rfloor +1}^3[0]\oplus Q_{\left\lfloor \frac{g}{2}\right\rfloor +1}^3[1]\), for any \(j\in S_r\). Let \(T_{2r}=V(Q_n^3)-\bigcup _{i\in S_{2r}}T_i\) and \(G_{r}=Q_n^3[T_{2r}]\).
Lemma 6
If \(g=1 \pmod {2}\), then
Proof
Let \(T_i\) and \(G_j\) be defined as above for any \(i\in S_{2r}\) and \(j\in S_r\), respectively. In light of definition of \(T_i\), we have \(\bigcup _{i\in S_{2r}}T_i=L_{2r\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }}^n\). By Lemma 1, \(2|E(Q_n^3[\bigcup _{i\in S_{2r}}T_i])|=ex_{2r\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }}(Q_n^3)\). Therefore,
\(\square\)
Lemma 7
For any \(i\in S_{r+1}\), the subgraph \(G_i\) is connected and \(\delta (G_i)\ge g\).
Proof
For any \(i\in S_r\), \(G_i\cong Q_{\left\lfloor \frac{g}{2}\right\rfloor +1}^3[0]\oplus Q_{\left\lfloor \frac{g}{2}\right\rfloor +1}^3\) [1], thereby, \(G_i\) is connected and \(\delta (G_i)\ge g\). In light of definition of \(T_i\), we have \(\bigcup _{i\in S_{2r}}T_i=L_{2r\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }}^n\) and \(T_{2r}=\overline{L_{2r\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }}^n}\). By Lemma 2, \(G_r\) is connected. Let \(2r=\sum _{j=0}^{s}a_j3^{k_j}\) be the ternary decomposition of 2r, \(k_j+\left\lfloor \frac{g}{2}\right\rfloor =l_j\). Then,
where \(n-1-h=l_s, b_h=3-a_s\) and
for \(0\le i\le h-1\). According to the above expression of \(r'\), \(b_i=0\) for some i’s. Therefore, \(r'\) can be rephrased as \(r'=\sum _{i=0}^{h'}b_i'3^{q_i}\), where \(q_0>q_1>\ldots >q_{h'}=l_s\) and \(b_{h'}'=3-a_s\). According to the construction of \(G_r\), each vertex in \(G_r\) falls in some \(Q_{q_i}^3\). Because of \(2(r+1)\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\le 3^n\), \(|G_r|\ge 2\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\). If \(q_{h'}=l_s=\left\lfloor \frac{g}{2}\right\rfloor\), then each vertex in \(Q_{q_{h'}}^3\) has at least one neighbor outside \(Q_{q_{h'}}^3\), and so \(\delta (G_r)\ge g\). If \(q_{h'}= l_s>\left\lfloor \frac{g}{2}\right\rfloor\), then \(\delta (G_r)\ge g\) in view of \(q_i\ge l_s>\left\lfloor \frac{g}{2}\right\rfloor\) for any \(i\in S_{h'+1}\). \(\square\)
Lemma 8
Let n, g, r be three integers such that \(2(r+1)\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\le 3^n\), where \(g=1 \pmod {2}\). Then
Proof
We prove this lemma by constructing a g-good-neighbor \((r+1)\)-component edge-cut with size \(2(2n-g)r\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }-(\frac{1}{2}ex_{2r}(Q_n^3)-r)\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\). Suppose that \(G_i\) is defined as above for any \(i\in S_{r+1}\). Then, by Lemma 7, \(Q_n^3-E(V(G_0), V(G_1), \ldots , V(G_r))\) is disconnected and has exactly \(r+1\) components \(G_0, G_1, \ldots , G_r\) and \(\delta (G_i)\ge g\) for any \(i\in S_{r+1}\). Moreover, \(|E(V(G_0), V(G_1), \ldots , V(G_{r-1}))|=(\frac{1}{2}ex_{2r}(Q_n^3)-r)\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\). Therefore, we have
Thus, the edge set \(E(V(G_0), V(G_1), \ldots , V(G_r))\) is a g-good-neighbor \((r+1)\)-component edge-cut with size \(2(2n-g)r\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }-(\frac{1}{2}ex_{2r}(Q_n^3)-r)\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\). By the definition of \(\lambda _{g, r+1}(Q_n^3)\), we have \(\lambda _{g, r+1}(Q_n^3)\le 2(2n-g)r\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }-(\frac{1}{2}ex_{2r}(Q_n^3)-r)\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }.\) \(\square\)
4 g-good-neighbor \((r+1)\)-component edge-connectivity
Define
As \(Q_n^3\) is 2n-regular, by the definition of \(ex_h(Q_n^3)\), we have
In this section, we will endeavor to establish the lower bound of g-good-neighbor \((r+1)\)-component edge-connectivity in \(Q_n^3\). In this process, we observe that the value of the lower bound is closely related to the function \(\zeta _h(Q_n^3)\). More specifically, it relies heavily on the monotonicity of \(\zeta _h(Q_n^3)\). Figure 3 depicts the image of the function \(\zeta _h(Q_7^3)\), it possesses a fractal structure and symmetry. In order to determine the exact value of \(\lambda _{g, r+1}(Q_n^3)\), based on a series of results by Xu et al. [22] and Zhang et al. [32] concerning the properties of the function \(\zeta _h(Q_n^3)\), we consider only two special cases that \(1\le (2-d)r\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\le (2-c)\cdot 3^{\big \lceil \frac{n}{2}\big \rceil -1}\) and \(r=3^{k_0}, 0\le k_0\le \left\lfloor \frac{n}{2}\right\rfloor -1\), \(0\le g\le 2(n-2k_0-1)\). In what follows, we review some properties of the function \(\zeta _h(Q_n^3)\).
We define
and
Lemma 9
[22] \(\zeta _h(Q_n^3)\) is increasing with respect to h in the interval \([1, (2-c)\cdot 3^{\big \lceil \frac{n}{2}\big \rceil }-2]\).
Lemma 10
[22] If \((2-c)\cdot 3^{\big \lceil \frac{n}{2}\big \rceil }-3\le h\le 3^{\big \lceil \frac{n+2-c}{2}\big \rceil }\) for \(n\ge 3\), then \(\zeta _h(Q_n^3)\ge \zeta _{(2-c)\cdot 3^{\big \lceil \frac{n}{2}\big \rceil }}(Q_n^3)\). In particular, \(\zeta _{(2-c)\cdot 3^{\big \lceil \frac{n}{2}\big \rceil }}(Q_n^3)=\zeta _{(2-c)\cdot 3^{\big \lceil \frac{n}{2}\big \rceil }-3}(Q_n^3)\).
Lemma 11
[22, 32] If \(3^k\le h \le 2\cdot 3^{n-1}\) for \(0\le k\le n-1\) and \(n\ge 3\), then \(\zeta _h(Q_n^3)\ge \zeta _{3^k}(Q_n^3)\). If \(2\cdot 3^k\le h \le 3^{n-1}\) for \(0\le k\le n-2\) and \(n\ge 3\), then \(\zeta _h(Q_n^3)\ge \zeta _{2\cdot 3^k}(Q_n^3)\).
Lemma 12
[27] For \(n\ge 3\) and \(0\le g\le 2n\), if H is a connected subgraph in \(Q_n^3\) with \(\delta (H)\ge g\), then \(|V(H)|\ge (2-d)3^{\left\lfloor \frac{g}{2}\right\rfloor }\).
Lemma 13
For \(n\ge 3\), if \(1\le (2-d)r\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\le (2-c)\cdot 3^{\big \lceil \frac{n}{2}\big \rceil -1}\) or \(r=3^{k_0}, 0\le k_0\le \left\lfloor \frac{n}{2}\right\rfloor -1\) and \(0\le g\le 2(n-2k_0-1)\), then
Proof
Let F be minimum g-good-neighbor \((r+1)\)-component edge-cut of \(Q_n^3\). By the minimality of F, \(Q_n^3-F\) has exactly \(r+1\) components, denoted by \(H_0, H_1, \ldots , H_r\), satisfying that the minimum degree of each component is at least g. Let \(|V(H_i)|=p_i\) for \(i\in S_{r+1}\). By Lemma 12, we have \(p_i\ge (2-d)\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\). Without loss of generality, suppose that \(p_0\ge p_1\ge \ldots \ge p_r\). Note that \(\bigg \lceil \frac{3^n}{r+1}\bigg \rceil \le p_0\le 3^n-r\cdot p_r\), we have
Therefore,
Case 1. \((2-d)r\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\le \sum _{i=1}^{r}p_i\le 2\cdot 3^{n-1}\).
In this scenario, by iteratively using Lemmas 9, 10 and 11, we have
Therefore,
Case 2. \(2\cdot 3^{n-1}<\sum _{i=1}^{r}p_i\le \left\lfloor \frac{r\cdot 3^n}{r+1}\right\rfloor\).
Case 2.1. \(1\le (2-d)r\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\le (2-c)\cdot 3^{\big \lceil \frac{n}{2}\big \rceil -1}\).
In this scenario, we have
By the symmetry of edge-cut, we have \(\zeta _{\sum _{i=1}^{r}p_i}(Q_n^3)=\zeta _{3^n-\sum _{i=1}^{r}p_i}(Q_n^3)\). By Lemmas 9 and 11,
holds. Therefore, by Lemmas 3 and 6, we have
Case 2.2. \(r=3^{k_0}\) and \(0\le g\le 2(n-2k_0-1)\), where \(0\le k_0\le \left\lfloor \frac{n}{2}\right\rfloor -1\).
In this scenario, we have
By the symmetry of edge-cut, we have \(\zeta _{\sum _{i=1}^{r}p_i}(Q_n^3)=\zeta _{3^n-\sum _{i=1}^{r}p_i}(Q_n^3)\). By Lemma 11,
holds. Therefore, by Lemmas 3 and 6, we have
Summing up above, we have
\(\square\)
Combining Lemma 13 with Lemmas 5 and 8, the following result is immediately obtained.
Theorem 2
Let n, g, r be three integers such that \(n\ge 3\), \(1\le (2-d)r\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\le (2-c)\cdot 3^{\big \lceil \frac{n}{2}\big \rceil -1}\) or \(r=3^{k_0}, 0\le k_0\le \left\lfloor \frac{n}{2}\right\rfloor -1\) and \(0\le g\le 2(n-2k_0-1)\). Then,
Corollary 1
[15, 22] (1) For \(n\ge 2\) and \(g\le n\), \(\lambda ^g(Q_n^3)=(2-d)(2n-g)3^{\left\lfloor \frac{g}{2}\right\rfloor }\).
(2) For \(n\ge 6\) and \(r\le 3^{\big \lceil \frac{n}{2}\big \rceil }\), \(c\lambda _{r+1}(Q_n^3)=2nr-\frac{ex_r(Q_n^3)}{2}\).
5 Application and comparisons
This work concentrates on the g-good-neighbor \((r+1)\)-component edge-connectivity under the conditions \(1\le (2-d)r\cdot 3^{\left\lfloor \frac{g}{2}\right\rfloor }\le (2-c)\cdot 3^{\big \lceil \frac{n}{2}\big \rceil -1}\) or \(r=3^{k_0}, 0\le k_0\le \left\lfloor \frac{n}{2}\right\rfloor -1\) and \(0\le g\le 2(n-2k_0-1)\). In what follows, we present an example in each of these two cases. For instance, let \(r=2\) and \(n=10\). In this case, \(r=2\) satisfies the former condition, hence, we have \(0\le g\le 8\). Based on the formulas of Theorem 2 and Corollary 1, we derive the corresponding values of \(\lambda _{g,3}(Q_{10}^3)\), \(\lambda ^{g}(Q_{10}^3)\) and \(c\lambda _{g+1}(Q_{10}^3)\) with respect to \(0\le g \le 8\) (see Table 3). Another example is \(r=3\) and \(n=9\). In this case, \(r=3\) satisfies the latter condition, hence, we deduce that \(0\le g\le 12\). Subsequently, we obtain the corresponding values of \(\lambda _{g,4}(Q_{9}^3)\), \(\lambda ^{g}(Q_{9}^3)\) and \(c\lambda _{g+1}(Q_{9}^3)\) with respect to \(0\le g \le 12\) in the same manner (see Table 3). As can be seen from Table 3, the value of \(\lambda _{g,3}(Q_{10}^3)\) is almost twice as large as \(\lambda ^{g}(Q_{10}^3)\) and much larger than the value of \(c\lambda _{g+1}(Q_{10}^3)\) regardless of the value of g. A similar conclusion can be drawn in \(Q_9^3\), the value of \(\lambda _{g,4}(Q_{9}^3)\) is almost three times the value of \(\lambda ^{g}(Q_{9}^3)\) and much larger than the value of \(c\lambda _{g+1}(Q_{9}^3)\).
The quantitative relationship among \(\lambda _{g,r+1}(Q_n^3)\), \(\lambda ^{g}(Q_{n}^3)\) and \(c\lambda _{g+1}(Q_{n}^3)\) can be clearly observed from Table 3. Next, we plot Figs. 4 and 5 to better present the growth rates of these three indicators as g increases. Consistent results can be observed that when r and n are fixed, \(\lambda _{g,r+1}(Q_n^3)\) grows at a rapid rate as g increases, whereas \(c\lambda _{g+1}(Q_{n}^3)\) is relatively flat. This implies that only a few failed links can disrupt this network to generate multiple components, but to allow each processor to communicate with more processors would require large-scale link failures. In addition, Figs. 6 and 7 depict the variation of \(\lambda _{g,r+1}(Q_n^3)\) with the growth of g for fixed n and r, respectively.
6 Concluding Remarks
This work suggests a novel indicator, namely g-good-neighbor r-component edge-connectivity, for measuring network reliability and fault tolerability of 3-ary n-cube, which is proposed by Liu et al. [17]. This concept breaks down the inherent idea to emphasize the double constraints on the resulting network in the presence of the large-scale faulty links, which not only limits the number of component in the resulting network, but also requires that each vertex is adjacent to at least g fault-free links. More importantly, g-good-neighbor \((r+1)\)-component edge-connectivity is almost r times the size of g-good-neighbor edge-connectivity and much larger than \((r+1)\)-component edge-connectivity in 3-ary n-cube. As a consequence, this metric offers a more refined quantitative indicator of the robustness of a multiprocessor system in the presence of link disruption.
Data availability
No datasets were generated or analyzed during the current study.
References
Adiga NR, Blumrich MA, Chen D, Coteus P, Gara A, Giampapa ME, Hei-delberger P, Singh S, Steinmacher-Burow BD, Takken T, Tsao M, Vranas P (2005) Blue Gene/L torus interconnection network. IBM J Res Dev 49(2–3):265–276
Anderson E, Brooks J, Grassl C, Scott S (1997) Performance of the CRAY T3E multiprocessor. In: Proceedings of the ACM/IEEE Conference on Supercomputing (SC’97), pp 1–17
Bhuyan L, Yang Q, Agrawal D (1989) Performance of multiprocessor intercommectionnetworks. Computer 22(2):25–37
Bondy JA, Murty USR (2008) Graph theory and its application. Academic Press, London
Chen L, Li X-J, Ma M (2022) Reliability assessment for modified bubble-sort networks. Discret Appl Math 307:88–94
Day K, Al-Ayyoub AE (1997) Fault diameter of \(k\)-ary \(n\)-cube networks. IEEE Trans Parallel Distrib Syst 8(9):903–907
Fan W, Fan J, Lin C, Wang Y, Han Y, Wang R (2019) Optimally embedding 3-ary \(n\)-cubes into grids. J Comput Sci Tech 34:372–387
Fǎbrega J, Fiol MA (1996) On the extraconnectivity of graphs. Discret Math 155:49–57
Fonseca P, Mota ES (2017) A survey on fault management in software-defined networks. IEEE Commun Surv Tutor 19(4):2284–2321
Hsieh S-Y, Lin T-J, Huang H-L (2007) Panconnectivity and edgepancyclicity of 3-ary \(n\)-cube. J Supercomput 42:225–233
Hsieh S-Y, Chang Y-H (2012) Extraconnectivity of \(k\)-ary \(n\)-cube networks. Theor Comput Sci 443:63–69
Kessler RE, Schwarzmeier JL Cray T3D: A new dimension for Cray research. In: 38th Annual IEEE Computer Society International Computer Conference-COMPCON SPRING ’93(Publ by IEEE, Piscataway, NJ, United States, San Fran-cisco, CA, USA, 1993), pp 176–182
Latifi S, Hegde M, Naraghi-Pour M (1994) Conditional connectivity measures for large miltiprocessor systems. IEEE Trans Comput 43:218–221
Li X-J, Xu J-M (2013) Edge-fault tolerance of hypercube-like networks. Inf Process Lett 113(19–21):760–763
Li S-Y, Li X-J, Ma M (2024) Reliability assessment for \(k\)-ary \(n\)-cubes with faulty edges. J Parallel Distrib Comput 27:104886
Liu D, Li P, Zhang B (2022) Component edge connectivity of hypercube-like networks. Theor Comput Sci 911:19–25
Liu H, Zhang M, Hsieh SY (2024) A novel links fault tolerant analysis: \(g\)-good \(r\)-component edge-connectivity of interconnection networks with applications to hypercube, IEEE Trans Reliab. https://doi.org/10.1109/TR.2024.3410526
Noakes MD, Wallach DA, Dally WJ (1993) The J-machine multicomputer: anarchitectural evaluation. Comput Arch News 21(2):224–235
Qiao H, Zhang M, Ma W, Yang X (2023) An \(O(\log (N))\) algorithm view: reliability evaluation of folded-crossed hypercube in terms of \(h\)-extra edge-connectivity. Parallel Process Lett 33:2350003
Sampathkumar E (1984) Connectivity of a graph-a generalization. J Comb Inf Syst Sci 9:71–78
Shang H, Sabir E, Meng J (2019) Conditional edge connectivity of the locally twisted cubes. J Oper Res Soc China 7(3):501–509
Xu L, Zhou S, Hsieh S-Y (2022) An \(O(\log _3 N)\) algorithm for reliability assessment of 3-ary \(n\)-cubes based on \(h\)-extra edge connectivity. IEEE Trans Reliab 71(3):1230–1240
Xu L, Zhou S (2022) An \(O(\log _2 N)\) algorithm for reliability assessment of augmented cubes based on \(h\)-extra edge-connectivity. J Supercomput 78(5):6739–6751
Xu L (2024) Fault tolerability evaluation for the component edge-connectivity of folded Petersen networks. Appl Math Comput 473:128673
Yang Y, Zhang M, Meng J (2023) Fault tolerance analysis for hamming graphs with large-scale faulty links based on \(r\)-component edge-connectivity. J Parallel Distrib Comput 173:107–114
Yang Y, Zhang M, Meng J (2024) Link fault tolerance of BC networks and folded hypercubes on \(h\)-extra \(r\)-component edge-connectivity. Appl Math Comput 462:128343
Yuan J, Liu A-X, Qin X, Zhang J-F, Li J (2016) \(g\)-Good-neighbor conditional diagnosability measures for 3-ary \(n\)-cube networks. Theor Comput Sci 626:144–162
Zhang M, Meng J, Yang W, Tian Y (2014) Reliability analysis of bijective connection networks in terms of the extra edge-connectivity. Inf Sci 279:374–382
Zhang M, Zhang L, Feng X, Lai H-J (2018) An \(O(\log _2 N)\) algorithm for reliability evaluation of \(h\)-extra edge-connectivity of folded hypercubes. IEEE Trans Reliab 67(1):297–307
Zhang M, Yang X, He X, Qin Z, Ma Y (2022) Reliability evaluation of augmented cubes on degree. J Interconnect Netw 22(1):2142019
Zhang Q, Xu L, Yang W (2021) Reliability analysis of the augmented cubes in terms of the extra edge-connectivity and the component edge-connectivity. J Parallel Distrib Comput 147:124–131
Zhang Q, Zhou S, Zhang H (2023) Reliability analysis of 3-ary \(n\)-cube in terms of average degree edge-connectivity. Discret Appl Math 341:31–39
Zhao S, Yang W, Zhang S, Xu L (2018) Component edge connectivity of hypercubes. Int J Found Comput Sci 29(6):995–1001
Acknowledgements
This work was partly supported by the National Natural Science Foundation of China (Nos. 61977016, 61572010, and 62277010), Natural Science Foundation of Fujian Province (Nos. 2020J01164, 2017J01738). This work was also partly supported by China Scholarship Council (CSC No. 202108350054).
Author information
Authors and Affiliations
Contributions
Qifan Zhang wrote the main manuscript text and prepared all figures. Shuming Zhou and Lulu Yang reviewed and edited the manuscript. All authors reviewed the manuscript.
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Zhang, Q., Zhou, S. & Yang, L. Link fault tolerability of 3-ary n-cube based on g-good-neighbor r-component edge-connectivity. J Supercomput 80, 24738–24757 (2024). https://doi.org/10.1007/s11227-024-06342-z
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-024-06342-z