Abstract
Classical connectivity is a vital metric to assess the reliability of interconnection networks, while it has defects in the defective assumption that all neighbours of one node may fail concurrently. To overcome this deficiency, many new generalizations of traditional connectivity, such as g-component (edge) connectivity, restricted (edge) connectivity, g-extra (edge) connectivity and so on, have been suggested. For any positive integer a, the a-regular edge connectivity of a connected graph G is the minimum cardinality of an edge cut, whose deletion disconnects G so that each component is a a-regular graph. In this work, we investigate the a-regular edge connectivity of some regular networks, which provides a novel idea for further exploring the reliability of networks. Finally, simulations are carried out to compare the a-regular connectivity with other types of connectivity in some regular networks. The comparison results imply that the a-regular edge connectivity has its superiority.
1. Introduction
It is well known that interconnection networks play a crucial role in designing a parallel computing system. Since the interconnection network topology is typically modeled by a connected graph G, graph theory has become an important tool for studying network performance, which has made fruitful contributions. Network reliability indicates the ability of the network to work even when some nodes or links fail. Traditionally, connectivity is one of the most significant metrics to evaluate the fault tolerance and reliability of networks. In general, the higher the connectivity is, the more reliable the interconnection network is. However, the connectivity (resp., edge connectivity) assumes that all vertices (resp., edges) adjacent to the same vertex in a graph could fail at the same time, which is impossible to happen in real networks.
Because there are some shortcomings in utilizing edge connectivity to measure the reliability of interconnection networks, Harary [Citation20] suggested the concept of conditional edge (vertex)-connectivity by imposing some conditions on the remaining components of the graph after some vertices and edges fail. Esfahanian and Hakimi [Citation13] characterized lower and upper bounds for the conditional edge-connectivity when satisfying a certain condition. Latter, researchers put forward novel generalizations of traditional connectivity, such as g-component edge connectivity, restricted (edge) connectivity, g-extra edge connectivity, embedded edge connectivity and so on.
Based on the number of connected components, g-component edge connectivity was introduced by Sampathkumar [Citation30]. A g-component edge cut of G is a set of edges whose deletion results in a graph with at least g components. The g-component edge connectivity of a graph G is the size of the smallest g-component edge cut of G. Zhao et al. [Citation39] explored the -component edge connectivity of n-dimensional hypercubes for , . Liu et al. [Citation26] determined the -component edge connectivity of the n-dimensional Hypercube-like networks for , .
Based on the number of vertices contained in each connected component, restricted connectivity was introduced by Esfahanian and Hakimi [Citation13]. At present, there are abundant research results in restricted (edge) connectivity. The k-restricted edge-connectivity has been applied successfully in the assessment of fault tolerance and reliability of networks. Liu and Meng [Citation28] determined the k-restricted edge-connectivity of the data center network DCell. Neil and Zoltan [Citation29] provided a generalization on edge-connectivity of permutation graphs for hypergraphs.
Fbrega and Fiol [Citation15] introduced the concept of g-extra edge connectivity. Let . If is disconnected, then the subset of edges X is said to be an edge cutset. If every component of has at least g + 1 vertices (g is a non-negative integer), then the edge cutset X is called an -edge cutset. The g-extra edge connectivity of Γ, denoted by , is then defined as the minimum cardinality over all -edge cutsets of Γ when Γ has at least one -edge cutset. Wei et al. [Citation33] established the g-extra edge-connectivity of balanced hypercubes , that is for .
Yang and Wang [Citation37] proposed the concept of the t-embedded edge connectivity. Let be an n-dimensional recursive network and let . A t-embedded edge cut of is a set F of edges in whose deletion disconnects and each vertex lies in a t-dimensional subnetwork of . The t-embedded edge connectivity is the cardinality of a minimum t-embedded edge cut. Latter, Li et al. [Citation24] determined the t-embedded edge connectivity of the bubble-sort graph , star graph and hypercube . They proved that for , and for . Yang [Citation34] showed that the t-embedded edge connectivity of the is for and odd . For further progress about connectivity of graphs, please refer to [Citation14, Citation18, Citation25, Citation27].
Based on regularity notion in chemical graph theory, the concepts of a-regular edge connectivity in (chemical) graph have been first proposed by Ediz and Çiftçi [Citation11]. For any positive integer a, the a-regular edge connectivity of a connected graph G is the minimum cardinality of an edge cut, whose deletion disconnects G that each component is a a-regular graph. They determined the k-regular connectivity for cycles, complete graphs, and Cartesian products of cycles. On this basis, we further investigate the a-regular edge connectivity of some regular networks, which provides a new method for further studying the reliability of networks in this work. Our main contributions are as follows.
We propose a general method to study the a-regular edge connectivity for Cayley graphs generated by transposition trees, and obtain the a-regular edge connectivity of star graph and bubble-sort graph .
We investigate for some BC graphs, and determine for the hypercube , twisted cube , crossed cube and Möbius cube .
We also determine the a-regular edge connectivity of alternating group graph and -star graph in a more intuitive way.
Furthermore, we make comparisons among regular networks by a simulation experiment and illustrate the comparison results. The comparison results imply that the a-regular edge connectivity has its superiority.
The remainder of this work proceeds as follows. We present the relevant definitions and notations in the next section. The main results and proofs are presented in Section 3. Section 4 concludes the work.
2. Preliminaries
In this paper, we only consider a simple, undirected, connected graph. For convenience of discussion, a graph G is a pair of sets , where V and E are the vertex-set and edge-set of G, respectively. The number of vertices in G is called the order of G, denoted by , while the number of edges in G is called the size of G, denoted by . Given an integer , let be the set and be the set of all the permutations on , that is, . For any , we denote as the neighbourhood of v in G. Moreover, the degree of a vertex v is represented as . Let , we use to denote the subgraph induced by the vertex subset in G. A graph is regular if all of its vertices have the same degree, and is k-regular if the regular degree is k. One 3-regular graph is sometimes called cubic. One 2-regular connected graph with n edges and n vertices is called cycle and denoted as . The edge connectivity λ is the minimum number of edges whose removal disconnects G. For any positive integer a, the a-regular edge connectivity of a connected graph G is the minimum cardinality of an edge cut, whose deletion disconnects G such that each component is a a-regular graph, denoted as . For undefined terms we refer the reader to [Citation4].
3. Main results
In this section, we provide the calculation of a-regular edge connectivity of Cayley graphs generated by transposition trees , BC graph , alternating group graph and -star graph . First, we give following lemmas.
Lemma 3.1
[Citation11]
Let G be a cycle with vertices, then for .
Lemma 3.2
[Citation11]
Let G be a complete graph, then for suitable integers n and a.
3.1. Cayley graphs generated by transposition trees
Let be a group and S be a subset of . If S is the generating set of , then . The Cayley graph is a digraph with vertex-set and arc-set . If , where , the Cayley graph is undirected. We use to denote a permutation on , and to denote a transposition which swaps the objects at ith and jth positions, such as . In this paper, we only discuss Cayley graph generated by transposition trees, which are defined as follows.
Definition 3.1
[Citation3]
Cayley graph generated by a transposition tree is denoted as . Vertices are all permutations on . Given a tree consisting of vertices , two vertices and in are adjacent, if and only if there is an edge (ij) in such that .
For convenience, we denote the Cayley graph generated by . When is isomorphic to a star, is the star graph [Citation2](see Figure ). When is isomorphic to a path, is the bubble sort graph [Citation2]. Without loss of generality, we may assume that and n is the leaf of with n−1 being its only neighbor. For example, is generated by a transposition tree in Figure .
Lemma 3.3
[Citation23, Citation32]
For n-dimensional Cayley graph , it has the following properties:
(1) | is a regular graph and has vertices; | ||||
(2) | For , the vertex set can be partitioned into n parts , where is the set of vertices with final digit number i. Obviously, for each , is isomorphic to ; | ||||
(3) | There are crossing edges between and . |
Theorem 3.1
For n-dimensional Cayley graph , then when and .
Proof.
First, we prove by induction on n. When n = 3, is a path. is a cycle of length 6, the theorem holds, where a = 1. When , suppose that holds. Now, it suffices to consider . Let n is the leaf of with n−1 being its only neighbor. Remove leaf n, the remaining graph is a tree with n−1 vertices. So is generated by . can be decomposed into n subgraphs by deleting number of cross edges. Let . Since a subgraph is disconnected and each component is a a-regular graph, we have . So .
Next, we prove . Let F be a minimum a-regular edge-cut and suppose that . That is to say, is a-regular. By Lemma 3.3, has edges. After deleting F, it leaves at least number of edges. Because is a regular graph, by Lemma 3.3 and handshaking lemma, the degree of each vertex is , which is not equal to a, a contradiction. Thus we have .
In summary, .
Corollary 3.1
For star graph , when and .
Corollary 3.2
For bubble-sort graph , when and .
3.2. BC graph
Definition 3.2
[Citation16]
The one-dimensional BC graph is the complete graph of two vertices. A graph G is a n-dimensional BC graph, denoted by , if there exist such that the following two conditions hold:
, and ;
The edges between and form a perfect matching M of G.
Lemma 3.4
[Citation31, Citation36]
The has the following common properties:
(1) | is n-regular, which has vertices and edges; | ||||
(2) | has the edge connectivity ; | ||||
(3) | each vertex in one -dimensional BC graph has exactly one neighbor in another -dimensional BC graph. |
Let and be the induced subgraphs and respectively. Then they are both -dimensional BC networks and . Obviously, and are isomorphic to . The edges between two subcubes are called cross edges. As an interconnection architecture, BC networks contain most of the variants of hypercube , such as the crossed cube [Citation12], the Möbius cube [Citation10] and the twisted cube [Citation21].
Theorem 3.2
For n-dimensional BC network, when and .
Proof.
It is clearly that can be decomposed into 2 subgraphs and by deleting cross edges.
First, we prove by induction on n. When n = 2. can be decomposed into 2 subgraphs and by deleting 2 number of cross edges, the theorem holds where a = 1. When , suppose that holds. Now, it suffices to consider . can be decomposed into 2 subgraphs by deleting number of cross edges. Let . Since a subgraph is disconnected and each component is a a-regular graph, we have . So .
Next, we prove . Let F be a minimum a-regular edge-cut and suppose that . That is to say, is a-regular. By Lemma 3.4, has edges. After deleting F, it leaves at least number of edges. Because is a regular graph, by Lemma 3.4 and handshaking lemma, the degree of each vertex is , which is not equal to a, a contradiction. Thus we have .
In summary, .
Corollary 3.3
when and .
3.3. Alternating group network
Definition 3.3
[Citation22]
The n-dimensional alternating group network is defined as the Cayley graph on the alternating group of degree n and generating set . Then in which two vertices u and v are adjacent if and only if v = us, where .
Lemma 3.5
[Citation5]
The alternating group network (see Figure ) has the following properties:
(1) | is a regular graph with vertices, edges and degree n−1. | ||||
(2) | can be decomposed into n sub-alternating group networks , where each fixes i in the last position of the label strings representing the vertices and is isomorphic to . |
Theorem 3.3
For n-dimensional , when and .
Proof.
It is clearly that can be decomposed into n subgraphs by deleting cross edges.
First, we prove by induction on n. When n = 4. can be decomposed into 4 subgraphs by deleting 6 number of cross edges, the theorem holds. When , suppose that holds where a = 2. Now, it suffices to consider . can be decomposed into n subgraphs by deleting number of cross edges. Let . Since a subgraph is disconnected and each component is a a-regular graph, we have . So .
Next, we prove . Let F be a minimum a-regular edge-cut and suppose that . That is to say, is a-regular. By Lemma 3.5, has edges. After deleting F, it leaves at least number of edges. Because is a regular graph, by Lemma 3.5 and handshaking lemma, the degree of each vertex is , which is not equal to a, a contradiction. Thus we have .
In summary, .
3.4. -star graph
Definition 3.4
[Citation8]
The -star graph, denoted by , is specified by two integers n and k, where . The node set of is denoted by and for }. The edge set of is defined as follows.
A node is adjacent to the node though an edge of dimension i, where .
A node is adjacent to the node though an edge of dimension 1, where (i.e. replace by x).
Lemma 3.6
[Citation7–9]
The -star graph (see Figure ) has the following properties:
(1) | is -regular and has vertices; | ||||
(2) | The set of all cross edges between any two subgraphs and is denoted by with order . | ||||
(3) | is isomorphic to the complete graph ; is isomorphic to the n-dimensional star graph ; is isomorphic to the n-dimensional alternating group graph ; | ||||
(4) | can be decomposed into n subgraphs where each subgraph fixes the symbol i in the last position k and is isomorphic to . |
Firstly, we consider when n = 3, is a triangle, then does not exist. is a 6-cycle , by Lemma 3.1, . Thus we only need to consider .
Theorem 3.4
For , if , then
Proof.
Case 1. k = 1, is isomorphic to the complete graph . By Lemma 3.2, we have .
Case 2. k = n−1, is isomorphic to the n-star graph . By Corollary 3.1, we have .
Case 3. k = n−2, is isomorphic to the n-dimensional alternating group graph . By Theorem 3.3, we have .
Case 4. .
First, we prove by induction on k. For k = 2. Since the set of all cross edges between any two subgraphs and is denoted by with order , it is clearly that can be decomposed into n subgraphs () by deleting cross edges. Since is isomorphic to the complete graph , by Lemma 3.6, we have , the desired. When k = 3, it is clearly that can be decomposed into n subgraphs () by deleting cross edges. Similar to the above method, we have . Then we suppose k=n−4 holds. We have . Now, it suffices to consider when k=n−3. It is clearly that can be decomposed into n subgraphs () by deleting cross edges. Similar to the above method, we have . Thus, we have .
Next, we prove . Let F be a minimum a-regular edge-cut and suppose that . Similar to the above method, we have . The result is desired.
In summary,
We compare the a-regular edge connectivity of some regular networks with other types of conditional connectivity, including component edge connectivity, restricted edge connectivity, extra edge connectivity, edge neighbor connectivity and embedded edge connectivity. The edge neighbor connectivity of a graph G is the minimum size of all edge-cut-strategies of G, where an edge-cut-strategy consists of a set of common edges of double stars whose removal disconnects the graph G or leaves a single vertex or 0. The summary of these conditional connectivity of regular networks , , , and are shown in Tables .
We make comparisons among for different values of the dimension n by a simulation experiment and illustrate the comparison results in Figure . In the simulation experiment, the parameter a in the regular edge connectivity are 2 and 3. As we can see from Figure that all these types of conditional connectivity are linear on n. If a is big, for example, when a = n−1, the value of regular edge connectivity can achieve , but all other kinds of conditional connectivity are linear on n. Thus the regular edge connectivity increases faster than all the other types of conditional connectivity since it has the greatest slope. We also make comparisons among and for different values of the dimension n by a simulation experiment and illustrate the comparison results in Figure . After simulating experiments, we get the same results for BC network, and (Figure ). When the dimension of a network is the same, the regular edge connectivity is higher than other classic edge connectivities. This shows that regular edge connectivity has better fault tolerability. It implies that the regular edge connectivity has its superiority.
4. Conclusions
With the development of network technology, network reliability analysis has witnessed a great progress in recent years. Based on the concept of a-regular edge connectivity, we determine the a-regular edge connectivity of some regular networks. In future work, we will explore more general graphs about the a-regular edge connectivity.
Disclosure statement
No potential conflict of interest was reported by the author(s).
Additional information
Funding
References
- M. Abdallah and C. Hung, Neighbor connectivity of the alternating group graph, J. Interconnect. Netw. 21(3) (2021), pp. 2150014.
- S.B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput. 38(4) (1989), pp. 555–566.
- N. Biggs and A. White, Permutation Groups and Combinatorial Structures, Cambridge University Press, London, Vol. 33, 1979.
- J. Bondy and U.S. Murty, Graph Theory, New York, Springer, 2008.
- B.-H. Chen, W.-J. Xiao, and B. Parhami, Internode distance and optimal routing in a class of alternating group networks, IEEE Trans. Comput. 55(12) (2006), pp. 1645–1648.
- Y.-J. Chen and S.-Y. Wang, The restricted edge connectivity of the bubble-sort, J. Taiyuan Norm Univ. 9(3) (2010), pp. 27–29.
- E. Cheng, K. Qiu, and Z.-Z. Shen, A note on the alternating group network, J. Supercomput. 59(1) (2012), pp. 246–248.
- W.-K. Chiang and R.-J. Chen, The (n,k)-star graph: A generalized star graph, Inf. Process. Lett. 56(5) (1995), pp. 259–264.
- W.-K. Chiang and R.-J. Chen, Topological properties of the (n,k)-star graph, Int. J. Found. Comput. Sci.9(2) (1998), pp. 235–248.
- P. Cull and S. Larson, The M o¨bius cubes, IEEE Trans. Comput. 44(5) (1995), pp. 647–659.
- S. Ediz and İ Çiftçi., On k-regular edge connectivity of chemical graphs, Main Group Met. Chem.45(1) (2022), pp. 106–110.
- K. Efe, The crossed cube architecture for parallel computation, IEEE Trans. Parallel. Distribut. Syst.3(5) (1992), pp. 513–524.
- A.-H. Esfahanian and S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27(4) (1988), pp. 195–199.
- J. Fàbrega and M.A. Fiol, Extraconnectivity of graphs with large girth, Discret. Math. 127(1–3) (1994), pp. 163–170.
- J. Fàbrega and M.A. Fiol, On the extraconnectivity of graphs, Discret. Math. 155(1–3) (1996), pp. 49–57.
- J.-X. Fan and L.-Q. He, BC interconnection networks and their properties, Chin. J. Comput. 26(1) (2003), pp. 84–90.
- Y.-Q. Feng, R.-X. Hao, and J.-X. Zhou, On computing of a conditional edge connectivity of alternating group network, Linear Multilinear A 65(12) (2017), pp. 2949–2507.
- J. Guo, M. Lu, and X. Wang, The (strong) structure connectivity and (strong) substructure connectivity of the (n,k)- bubble-sort network, Appl. Math. Comput. 425 (2022), pp. 127078.
- L.-T. Guo, M.-Z. Zhang, S.-H. Zhai, and L.-Q. Xu, Relation of extra edge connectivity and component edge connectivity for regular networks, Int. J. Found. Comput. S 32(2) (2021), pp. 137–149.
- F. Harary, Conditional connectivity, Networks 13(3) (1983), pp. 347–357.
- P. Hibers, M. Koopman, and D. Snepscheut, The twisted cube, in Proc. Conf. Parallel Architectures and Languages Europe, Springer, Berlin, Heidelberg, 1987, pp. 152–159.
- Y.-H. Ji, A new class of Cayley networks based on the alternating groups, Adv. Math. 27 (1998), pp. 361–362.
- S. Lakshmivarahan, J.-S. Jwo, and S. Dhall, Symmetry in interconnection networks based on cayley graphs of permutation groups a survey, Parallel Comput. 19(4) (1993), pp. 361–407.
- X.-J. Li, Q.-Q. Dong, Z. Yan, and J.-M. Xu, Embedded connectivity of recursive networks, Theor. Comput. Sci. 653 (2016), pp. 79–86.
- X.-J. Li, X.-Q. Zeng, and J.-M. Xu, Note on reliability evaluation of arrangement graphs, Appl. Math. Comput. 418 (2022), pp. 126845.
- D. Liu, P.-S. Li, and B.-C. Zhang, Component edge connectivity of hypercube-like networks, Theor. Comput. Sci. 911 (2022), pp. 19–25.
- F.-X. Liu and J.-X. Meng, Edge-connectivity of regular graphs with two orbits, Discret. Math. 308(16) (2008), pp. 3711–3716.
- X.-M. Liu and J.-X. Meng, The k-restricted edge-connectivity of the data center network DCell, Appl. Math. Comput. 396(1) (2021), pp. 113614.
- J. Neil and S. Zoltan, Edge-connectivity of permutation hypergraphs, Discrete Math. 32 (2012), pp. 2536–2539.
- E. Sampathkumar, Connectivity of a graph-a generalization, J. Comb. Inf. Syst. Sci. 9(2) (1984), pp. 71–78.
- A. Vaidya, P. Rao, and S. Shankar, A class of hypercube-like networks, in Proceedings of the 5th Symposium on Parallel and distributed Processing. IEEE Computer Soc, Vol. 193, pp. 800–803.
- M. Wan and Z. Zhang, A kind of conditional vertex connectivity of star graphs, Appl. Math. Lett.22(2) (2009), pp. 264–267.
- Y.-L. Wei, R.-H. Li, and W.-H. Yang, The g-extra edge-connectivity of balanced hypercubes, J. Interconnect. Netw. 21(4) (2021), pp. 2142008.
- Y.-X. Yang, Embedded edge connectivity of k-ary n-cubes, Inf. Process. Lett. 180 (2023), pp. 106328.
- W.-H. Yang, H.-Z. Li, and J.-X. Meng, Conditional connectivity of Cayley graphs generated by transposition trees, Inform. Process. Lett. 110(23) (2010), pp. 1027–1030.
- W.-H. Yang and H.-Q. Lin, Reliability evaluation of BC networks in terms of the extra vertex- and edge-connectivity, IEEE Trans. Comput. 63(10) (2014), pp. 2540–2548.
- Y.-X. Yang and S.-Y. Wang, Conditional connectivity of star graph networks under embedding restriction, Inform. Sci. 199 (2012), pp. 187–192.
- H. Zhang, S.-M. Zhou, and E. Cheng, Restricted connectivity of Cayley graph generated by transposition trees, Discret. Appl. Math. 327 (2023), pp. 87–95.
- S.-L. Zhao, W.-H. Yang, S.-R. Zhang, and L.-Q. Xu, Component edge connectivity of hypercubes, Int. J. Found. Comput. Sci. 29(6) (2018), pp. 995–1001.