The regular edge connectivity of regular networks

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.

KEYWORDS:

• Interconnection networks
• connectivity
• a-regular edge connectivity
• regular networks

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 [20] 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 [13] 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 $c{\lambda }_g\left(G\right)$ was introduced by Sampathkumar [30]. 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 $c{\lambda }_g\left(G\right)$ of a graph G is the size of the smallest g-component edge cut of G. Zhao et al. [39] explored the $(g+1)$-component edge connectivity of n-dimensional hypercubes for $1\le \mathrm{g}\le 2^{\left[\frac{n}{2}\right]}$, $n\ge 7$. Liu et al. [26] determined the $(g+1)$-component edge connectivity of the n-dimensional Hypercube-like networks for $1\le g\le 2^{\lceil \frac{n}{2}\rceil }$, $n\ge 8$.

Based on the number of vertices contained in each connected component, restricted connectivity was introduced by Esfahanian and Hakimi [13]. 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 [28] determined the k-restricted edge-connectivity of the data center network DCell. Neil and Zoltan [29] provided a generalization on edge-connectivity of permutation graphs for hypergraphs.

F$\stackrel{`}{a}$brega and Fiol [15] introduced the concept of g-extra edge connectivity. Let $X\subseteq E\left(\mathrm{\Gamma }\right)$. If $\mathrm{\Gamma }-X$ is disconnected, then the subset of edges X is said to be an edge cutset. If every component of $\mathrm{\Gamma }-X$ has at least g + 1 vertices (g is a non-negative integer), then the edge cutset X is called an $R_g$-edge cutset. The g-extra edge connectivity of Γ, denoted by ${\lambda }_g\left(\mathrm{\Gamma }\right)$, is then defined as the minimum cardinality over all $R_g$-edge cutsets of Γ when Γ has at least one $R_g$-edge cutset. Wei et al. [33] established the g-extra edge-connectivity of balanced hypercubes $B{H}_n$, that is ${\lambda }_g\left(B{H}_n\right)=2(g+1)n-4g+4$ for $n>6-\frac{12}{g+1}$.

Yang and Wang [37] proposed the concept of the t-embedded edge connectivity. Let $G_n$ be an n-dimensional recursive network and let $0\le t\le n-1$. A t-embedded edge cut of $G_n$ is a set F of edges in $G_n$ whose deletion disconnects $G_n$ and each vertex lies in a t-dimensional subnetwork of $G_n-F$. The t-embedded edge connectivity ${\eta }_t\left(G_n\right)$ is the cardinality of a minimum t-embedded edge cut. Latter, Li et al. [24] determined the t-embedded edge connectivity of the bubble-sort graph $B_n$, star graph $S_n$ and hypercube $Q_n$. They proved that ${\eta }_3\left(B_n\right)=6n-18$ for $n\ge 4$, ${\eta }_t\left(S_n\right)=t!\left(n-t\right)$ and ${\eta }_t\left(Q_n\right)=\left(n-t\right)2^t$ for $1\le t\le n-1$. Yang [34] showed that the t-embedded edge connectivity of the $Q_n^k$ is ${\eta }_t\left(Q_n^k\right)=2(n-k)k^t$ for $1\le t\le n-1$ and odd $k\ge 3$. For further progress about connectivity of graphs, please refer to [14, 18, 25, 27].

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 [11]. 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.

1. 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 $S_n$ and bubble-sort graph $B_n$.

2. We investigate ${\lambda }^{ar}\left(G\right)$ for some BC graphs, and determine ${\lambda }^{ar}\left(G\right)$ for the hypercube $Q_n$, twisted cube $LT{Q}_n$, crossed cube $FC{Q}_n$ and Möbius cube $M{Q}_n$.

3. We also determine the a-regular edge connectivity of alternating group graph $A{N}_n$ and $(n,k)$-star graph $S_{n,k}$ in a more intuitive way.

4. 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 $(V,E)$, 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 $|V\left(G\right)|$, while the number of edges in G is called the size of G, denoted by $|E\left(G\right)|$. Given an integer $n\ge 2$, let $\left[n\right]$ be the set $\left\{1,2,\dots ,n\right\}$ and $P\left(n\right)$ be the set of all the permutations on $\left[n\right]$, that is, $P\left(n\right)=\left\{p_1{p}_2\cdots p_n|p_i\in \left[n\right],and{p}_i\ne p_{j}for1\le i\ne j\le n\right\}$. For any $v\in V\left(G\right)$, we denote $N_G\left(v\right)=\{w\in V(G)\mid (v,w)\in E(G\left)\right\}$ as the neighbourhood of v in G. Moreover, the degree of a vertex v is represented as $d_v=|N_G\left(v\right)|$. Let $V^{\prime }\subset V\left(G\right)$, we use $G\left[V^{\prime }\right]$ to denote the subgraph induced by the vertex subset $V^{\prime }$ 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 $C_n$. 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 ${\lambda }^{ar}\left(G\right)$. For undefined terms we refer the reader to [4]. 

3. Main results

In this section, we provide the calculation of a-regular edge connectivity of Cayley graphs generated by transposition trees ${\mathrm{\Gamma }}_n$, BC graph ${\mathcal{B}}_n$, alternating group graph $A{N}_n$ and $(n,k)$-star graph $S_{n,k}$. First, we give following lemmas.

Lemma 3.1

[11]

Let G be a cycle with $2n$ vertices, then ${\lambda }^{1r}\left(G\right)=n$ for $n\ge 2$.

Lemma 3.2

[11]

Let G be a complete graph, then ${\lambda }^{ar}\left(G\right)=\frac{n(n-a-1)}{2}$ for suitable integers n and a.

3.1. Cayley graphs generated by transposition trees

Let $\mathrm{\Gamma }$ be a group and S be a subset of $\mathrm{\Gamma }$. If S is the generating set of $\mathrm{\Gamma }$, then $\mathrm{\Gamma }=〈S〉$. The Cayley graph $Cay(\mathrm{\Gamma },S)$ is a digraph with vertex-set $V\left(Cay\right(\mathrm{\Gamma },S\left)\right)=\mathrm{\Gamma }$ and arc-set $\left\{\left(h,hx\right)|h\in \mathrm{\Gamma },x\in S\right\}$. If $S=S^{-1}$, where $S^{-1}=\left\{x^{-1}|x\in S\right\}$, the Cayley graph $Cay(\mathrm{\Gamma },S)$ is undirected. We use $\left(p_1{p}_2\cdots p_n\right)$ to denote a permutation on $\left\{1,2,\dots ,n\right\}$, and $\left[ij\right]$ to denote a transposition which swaps the objects at ith and jth positions, such as $\left(p_1\cdots p_i\cdots p_j\cdots p_n\right)\left[ij\right]=\left(p_1\cdots p_j\cdots p_i\cdots p_n\right)$. In this paper, we only discuss Cayley graph generated by transposition trees, which are defined as follows.

Definition 3.1

[3]

Cayley graph generated by a transposition tree is denoted as ${\mathrm{\Gamma }}_n$. Vertices are all permutations on $\left\{1,2,\dots ,n\right\}$. Given a tree $G\left(\mathrm{\Gamma }\right)$ consisting of vertices $\left\{1,2,\dots ,n\right\}$, two vertices $\left(p_1{p}_2\cdots p_n\right)$ and $\left(q_1{q}_2\cdots q_n\right)$ in ${\mathrm{\Gamma }}_n$ are adjacent, if and only if there is an edge (ij) in $G\left(\mathrm{\Gamma }\right)$ such that $\left(p_1{p}_2\cdots p_n\right)\left[ij\right]=\left(q_1{q}_2\cdots q_n\right)$.

For convenience, we denote ${\mathrm{\Gamma }}_n$ the Cayley graph generated by $G\left(\mathrm{\Gamma }\right)$. When $G\left(\mathrm{\Gamma }\right)$ is isomorphic to a star, ${\mathrm{\Gamma }}_n$ is the star graph $S_n$ [2](see Figure 2). When $G\left(\mathrm{\Gamma }\right)$ is isomorphic to a path, ${\mathrm{\Gamma }}_n$ is the bubble sort graph $B_n$ [2]. Without loss of generality, we may assume that $V\left(G\left(\mathrm{\Gamma }\right)\right)=\left\{1,2,\dots ,n\right\}$ and n is the leaf of $G\left(\mathrm{\Gamma }\right)$ with n−1 being its only neighbor. For example, $G\left(\mathrm{\Gamma }\right)$ is generated by a transposition tree ${\mathrm{\Gamma }}_4$ in Figure 1.

Figure 1. $G\left(\mathrm{\Gamma }\right)$ generated by a transposition tree ${\mathrm{\Gamma }}_4$.

Lemma 3.3

[23, 32]

For n-dimensional Cayley graph ${\mathrm{\Gamma }}_n$, it has the following properties:

(1)	${\mathrm{\Gamma }}_n$ is a $(n-1)$ regular graph and has $n!$ vertices;
(2)	For ${\mathrm{\Gamma }}_n$, the vertex set $V\left({\mathrm{\Gamma }}_n\right)$ can be partitioned into n parts $V\left({\mathrm{\Gamma }}_n^1\right),V\left({\mathrm{\Gamma }}_n^2\right),\dots ,V\left({\mathrm{\Gamma }}_n^n\right)$, where $V\left({\mathrm{\Gamma }}_n^i\right)$ is the set of vertices with final digit number i. Obviously, for each $1\le i\le n$, ${\mathrm{\Gamma }}_n^i$ is isomorphic to ${\mathrm{\Gamma }}_{n-1}$;
(3)	There are $(n-2)!$ crossing edges between ${\mathrm{\Gamma }}_n^i$ and ${\mathrm{\Gamma }}_n^j$.

Theorem 3.1

For n-dimensional Cayley graph ${\mathrm{\Gamma }}_n$, then ${\lambda }^{ar}\left({\mathrm{\Gamma }}_n\right)=\frac{n!(n-a-1)}{2}$ when $1\le a\le n-2$ and $n\ge 3$.

Proof.

First, we prove ${\lambda }^{ar}\left({\mathrm{\Gamma }}_n\right)\le \frac{n!(n-a-1)}{2}$ by induction on n. When n = 3, $G\left(\mathrm{\Gamma }\right)$ is a $P_3$ path. ${\mathrm{\Gamma }}_3$ is a cycle of length 6, the theorem holds, where a = 1. When $n\ge 4$, suppose that ${\lambda }^{ar}\left({\mathrm{\Gamma }}_{n-1}\right)\le \frac{(n-1)!\left(n-1-a-1\right)}{2}=\frac{(n-1)!\left(n-a-2\right)}{2}$ holds. Now, it suffices to consider ${\mathrm{\Gamma }}_n$. Let n is the leaf of $G\left(\mathrm{\Gamma }\right)$ with n−1 being its only neighbor. Remove leaf n, the remaining graph $G\left({\mathrm{\Gamma }}^{\mathrm{\prime }}\right)$ is a tree with n−1 vertices. So ${\mathrm{\Gamma }}_{n-1}$ is generated by $G\left({\mathrm{\Gamma }}^{\mathrm{\prime }}\right)$. ${\mathrm{\Gamma }}_n$ can be decomposed into n subgraphs ${\mathrm{\Gamma }}_n^i(\cong {\mathrm{\Gamma }}_{n-1})$ by deleting $\frac{n!\left(n-1\right)}{2}-n\cdot \frac{(n-1)!(n-2)}{2}=\frac{n!}{2}$ number of cross edges. Let $\left|F^{\mathrm{\prime }}\right|={\lambda }^{ar}\left({\mathrm{\Gamma }}_{n-1}\right)\le \frac{(n-1)!\left(n-a-2\right)}{2}$. Since a subgraph ${\mathrm{\Gamma }}_{n-1}-F^{\mathrm{\prime }}$ is disconnected and each component is a a-regular graph, we have $\left|F\right|=\frac{n!}{2}+n\left|F^{\mathrm{\prime }}\right|$. So ${\lambda }^{ar}\left({\mathrm{\Gamma }}_n\right)\le \frac{n!}{2}+n{\lambda }^{ar}\left({\mathrm{\Gamma }}_{n-1}\right)=\frac{n!(n-a-1)}{2}$.

Figure 2. Bubble-sort $B_4$ graph.

Figure 3. $A{N}_4$.

Figure 4. The (4,2)-star graph $S_{4,2}$.

Next, we prove ${\lambda }^{ar}\left({\mathrm{\Gamma }}_n\right)\ge \frac{n!(n-a-1)}{2}$. Let F be a minimum a-regular edge-cut and suppose that $\left|F\right|\le \frac{n!\left(n-a-1\right)}{2}-1$. That is to say, ${\mathrm{\Gamma }}_n-F$ is a-regular. By Lemma 3.3, ${\mathrm{\Gamma }}_n$ has $\frac{n!\left(n-1\right)}{2}$ edges. After deleting F, it leaves at least $\frac{n!\left(n-1\right)}{2}-(\frac{n!\left(n-a-1\right)}{2}-1)=\frac{n!a}{2}+1$ number of edges. Because ${\mathrm{\Gamma }}_n-F$ is a regular graph, by Lemma 3.3 and handshaking lemma, the degree of each vertex is $a+\frac{2}{n!}$, which is not equal to a, a contradiction. Thus we have ${\lambda }^{ar}\left({\mathrm{\Gamma }}_n\right)\ge \frac{n!(n-a-1)}{2}$.

In summary, ${\lambda }^{ar}\left({\mathrm{\Gamma }}_n\right)=\frac{n!(n-a-1)}{2}$.

Corollary 3.1

For star graph $S_n$, ${\lambda }^{ar}\left(S_n\right)=\frac{n!(n-a-1)}{2}$ when $1\le a\le n-2$ and $n\ge 3$.

Corollary 3.2

For bubble-sort graph $B_n$, ${\lambda }^{ar}\left(B_n\right)=\frac{n!(n-a-1)}{2}$ when $1\le a\le n-2$ and $n\ge 3$.

3.2. BC graph

Definition 3.2

[16]

The one-dimensional BC graph is the complete graph of two vertices. A graph G is a n-dimensional BC graph, denoted by ${\mathcal{B}}_n$, if there exist $V_0,V_1\subset V\left(G\right)$ such that the following two conditions hold:

1. $V\left(G\right)=V_0\cup V_1,V_0\ne \mathrm{\varnothing },V_1\ne \mathrm{\varnothing },V_0\cap V_1=\mathrm{\varnothing }$, and $G\left[V_0\right],G\left[V_1\right]\in {\mathcal{B}}_{n-1}$;

2. The edges between $V_0$ and $V_1$ form a perfect matching M of G.

Lemma 3.4

[31, 36]

The ${\mathcal{B}}_n$ has the following common properties:

(1)	${\mathcal{B}}_n$ is n-regular, which has $2^n$ vertices and $n\cdot 2^{n-1}$ edges;
(2)	${\mathcal{B}}_n$ has the edge connectivity $\lambda \left({\mathcal{B}}_n\right)=n$;
(3)	each vertex in one $(n-1)$-dimensional BC graph has exactly one neighbor in another $(n-1)$-dimensional BC graph.

Let ${\mathcal{B}}_{n-1}^0$ and ${\mathcal{B}}_{n-1}^1$ be the induced subgraphs ${\mathcal{B}}_n\left[V_0\right]$ and ${\mathcal{B}}_n\left[V_1\right]$ respectively. Then they are both $(n-1)$-dimensional BC networks and ${\mathcal{B}}_n={\mathcal{B}}_{n-1}^0\oplus {\mathcal{B}}_{n-1}^1$. Obviously, ${\mathcal{B}}_{n-1}^0$ and ${\mathcal{B}}_{n-1}^1$ are isomorphic to ${\mathcal{B}}_{n-1}$. The edges between two subcubes are called cross edges. As an interconnection architecture, BC networks contain most of the variants of hypercube $Q_n$, such as the crossed cube $C{Q}_n$ [12], the Möbius cube $M{Q}_n$ [10] and the twisted cube $T{Q}_n$ [21].

Theorem 3.2

For n-dimensional BC network, ${\lambda }^{ar}\left({\mathcal{B}}_n\right)=2^{n-1}(n-a)$ when $1\le a\le n-1$ and $n\ge 2$.

Proof.

It is clearly that ${\mathcal{B}}_n$ can be decomposed into 2 subgraphs ${\mathcal{B}}_{n-1}^0$ and ${\mathcal{B}}_{n-1}^1$ by deleting $2^{n-1}$ cross edges.

First, we prove ${\lambda }^{ar}\left({\mathcal{B}}_n\right)\le 2^{n-1}(n-a)$ by induction on n. When n = 2. ${\mathcal{B}}_2$ can be decomposed into 2 subgraphs ${\mathcal{B}}_1^0$ and ${\mathcal{B}}_1^1$ by deleting 2 number of cross edges, the theorem holds where a = 1. When $n\ge 3$, suppose that ${\lambda }^{ar}\left({\mathcal{B}}_{n-1}\right)\le 2^{n-2}\left(n-1-a\right)$ holds. Now, it suffices to consider ${\mathcal{B}}_n$. ${\mathcal{B}}_n$ can be decomposed into 2 subgraphs ${\mathcal{B}}_{n-1}^i(\cong {\mathcal{B}}_{n-1})$ by deleting $2^{n-1}$ number of cross edges. Let $|F^{\mathrm{\prime }}|={\lambda }^{ar}\left({\mathcal{B}}_{n-1}\right)\le 2^{n-2}\left(n-1-a\right)$. Since a subgraph ${\mathcal{B}}_{n-1}-F^{\mathrm{\prime }}$ is disconnected and each component is a a-regular graph, we have $|F|=2^{n-1}+2|F^{\mathrm{\prime }}|$. So ${\lambda }^{ar}\left({\mathcal{B}}_n\right)\le 2^{n-1}(n-a)$.

Next, we prove ${\lambda }^{ar}\left({\mathcal{B}}_n\right)\ge 2^{n-1}(n-a)$. Let F be a minimum a-regular edge-cut and suppose that $|F|\le 2^{n-1}\left(n-a\right)-1$. That is to say, ${\mathcal{B}}_n-F$ is a-regular. By Lemma 3.4, ${\mathcal{B}}_n$ has $n\cdot 2^{n-1}$ edges. After deleting F, it leaves at least $n\cdot 2^{n-1}-\left(2^{n-1}\right(n-a)-1)=2^{n-1}\cdot a+1$ number of edges. Because ${\mathcal{B}}_n-F$ is a regular graph, by Lemma 3.4 and handshaking lemma, the degree of each vertex is $a+\frac{2}{2^n}$, which is not equal to a, a contradiction. Thus we have ${\lambda }^{ar}\left({\mathcal{B}}_n\right)\ge 2^{n-1}(n-a)$.

In summary, ${\lambda }^{ar}\left({\mathcal{B}}_n\right)=2^{n-1}(n-a)$.

Corollary 3.3

${\lambda }^{ar}\left(Q_n\right)={\lambda }^{ar}\left(LT{Q}_n\right)={\lambda }^{ar}\left(FC{Q}_n\right)={\lambda }^{ar}\left(M{Q}_n\right)=2^{n-1}(n-a)$ when $1\le a\le n-1$ and $n\ge 2$.

3.3. Alternating group network $A{N}_n$

Definition 3.3

[22]

The n-dimensional alternating group network $A{N}_n$ is defined as the Cayley graph on the alternating group $A_n$ of degree n and generating set $S=\left\{\left(123\right),\left(132\right)\right\}\cup \left\{\left(12\right)\left(3i\right)|4\le i\le n\right\}$. Then $V\left(A{N}_n\right)=A_n$ in which two vertices u and v are adjacent if and only if v = us, where $s\in S$.

Lemma 3.5

[5]

The alternating group network $A{N}_n$ (see Figure 3) has the following properties:

(1)	$A{N}_n$ is a regular graph with $\frac{n!}{2}$ vertices, $\frac{n!\left(n-1\right)}{4}$ edges and degree n−1.
(2)	$A{N}_n$ can be decomposed into n sub-alternating group networks $A{N}_n^1,A{N}_n^2,\dots ,A{N}_n^n$, where each $A{N}_n^i$ fixes i in the last position of the label strings representing the vertices and is isomorphic to $A{N}_{n-1}$.

Theorem 3.3

For n-dimensional $A{N}_n$, ${\lambda }^{ar}\left(A{N}_n\right)=\frac{n!\left(n-1-a\right)}{4}$ when $2\le a\le n-2$ and $n\ge 4$.

Proof.

It is clearly that $A{N}_n$ can be decomposed into n subgraphs $A{N}_n^i(i\in \{1,2,\dots ,n\left\}\right)$ by deleting $\frac{(n-1)!}{2}\cdot n\cdot \frac{1}{2}=\frac{n!}{4}$ cross edges.

First, we prove ${\lambda }^{ar}\left(A{N}_n\right)\le \frac{n!\left(n-1-a\right)}{4}$ by induction on n. When n = 4. $A{N}_4$ can be decomposed into 4 subgraphs $A{N}_4^i(\cong A{N}_3)$ by deleting 6 number of cross edges, the theorem holds. When $n\ge 5$, suppose that ${\lambda }^{ar}\left(A{N}_{n-1}\right)\le \frac{(n-1)!(n-a-2)}{4}$ holds where a = 2. Now, it suffices to consider $A{N}_n$. $A{N}_n$ can be decomposed into n subgraphs $A{N}_n^i(\cong A{N}_{n-1})$ by deleting $\frac{n!}{4}$ number of cross edges. Let $|F^{\mathrm{\prime }}|={\lambda }^{ar}\left(A{N}_{n-1}\right)\le \frac{(n-1)!(n-a-2)}{4}$. Since a subgraph $A{N}_{n-1}-F^{\mathrm{\prime }}$ is disconnected and each component is a a-regular graph, we have $|F|=\frac{n!}{4}+n|F^{\mathrm{\prime }}|$. So ${\lambda }^{ar}\left(A{N}_n\right)=\frac{n!}{4}+n{\lambda }^{ar}\left(A{N}_{n-1}\right)\le \frac{n!(n-a-1)}{4}$.

Next, we prove ${\lambda }^{ar}\left(A{N}_n\right)\ge \frac{n!(n-a-1)}{4}$. Let F be a minimum a-regular edge-cut and suppose that $|F|\le \frac{n!(n-a-1)}{4}-1$. That is to say, $A{N}_n-F$ is a-regular. By Lemma 3.5, $A{N}_n$ has $\frac{n!\left(n-1\right)}{4}$ edges. After deleting F, it leaves at least $\frac{n!\left(n-1\right)}{4}-\left(\frac{n!\left(n-a-1\right)}{4}-1\right)=\frac{n!a}{4}+1$ number of edges. Because $A{N}_n-F$ is a regular graph, by Lemma 3.5 and handshaking lemma, the degree of each vertex is $a+\frac{4}{n!}$, which is not equal to a, a contradiction. Thus we have ${\lambda }^{ar}\left(A{N}_n\right)\ge \frac{n!(n-a-1)}{4}$.

In summary, ${\lambda }^{ar}\left(A{N}_n\right)=\frac{n!\left(n-1-a\right)}{4}$.

3.4. $(n,k)$-star graph $S_{n,k}$

Definition 3.4

[8]

The $(n,k)$-star graph, denoted by $S_{n,k}$, is specified by two integers n and k, where $1\le k\le n$. The node set of $S_{n,k}$ is denoted by $V\left(S_{n,k}\right)=\{p_1{p}_2\cdots p_k|p_k\in 〈n〉=\{1,2,\dots ,n\},$ and $p_i\ne p_j$ for $i\ne j$}. The edge set of $S_{n,k}$ is defined as follows. 

1. A node $p_1{p}_2\cdots p_i\cdots p_k$ is adjacent to the node $p_i{p}_2\cdots p_1\cdots p_k$ though an edge of dimension i, where $2\le i\le k$. 

2. A node $p_1{p}_2\cdots p_i\cdots p_k$ is adjacent to the node $x{p}_2\cdots p_i\cdots p_k$ though an edge of dimension 1, where $\in 〈n〉\mathrm{\setminus }\{p_1{p}_2\cdots p_i\cdots p_k\}$ (i.e. replace $p_1$ by x).

Lemma 3.6

[7–9]

The $(n,k)$-star graph $S_{n,k}$ (see Figure 4) has the following properties:

(1)	$S_{n,k}$ is $(n-1)$-regular and has $\frac{n!}{\left(n-k\right)!}$ vertices;
(2)	The set of all cross edges between any two subgraphs $S_{n,k}^i$ and $S_{n,k}^j(i\ne j\in 〈n〉)$ is denoted by $E(i,j)$ with order $|E(i,j)|=\frac{(n-2)!}{\left(n-k\right)!}$.
(3)	$S_{n,1}$ is isomorphic to the complete graph $K_n$; $S_{n,n-1}$ is isomorphic to the n-dimensional star graph $S_n$; $S_{n,n-2}$ is isomorphic to the n-dimensional alternating group graph $A{N}_n$;
(4)	$S_{n,1}$ can be decomposed into n subgraphs $S_{n,k}^1,S_{n,k}^2,\dots ,S_{n,k}^i$ where each subgraph $S_{n,k}^i$ fixes the symbol i in the last position k and is isomorphic to $S_{n-1,k-1}$.

Firstly, we consider when n = 3, $S_{3,1}$ is a triangle, then ${\lambda }^{1r}\left(S_{3,1}\right)$ does not exist. $S_{3,2}$ is a 6-cycle $C_6$, by Lemma 3.1, ${\lambda }^{1r}\left(S_{3,1}\right)=3$. Thus we only need to consider $n\ge 4$.

Theorem 3.4

For $n\ge 4$, if $1\le k\le n-1$, then ${\lambda }^{ar}\left(S_{n,k}\right)=\{\begin{array}{l}{\displaystyle \frac{n(n-a-1)}{2}},k=1\\ \begin{array}{l}{\displaystyle \frac{n!(n-a-1)}{2}},k=n-1\\ {\displaystyle \frac{n!(n-a-1)}{4}},k=n-2\end{array}\\ {\displaystyle \frac{n(n-1)(n-2)\cdots (n-k+1)}{2}}(n-3),2\le k\le n-3.\end{array}$

Proof.

Case 1. k = 1, $S_{n,1}$ is isomorphic to the complete graph $K_n$. By Lemma 3.2, we have ${\lambda }^{ar}\left(S_{n,1}\right)={\lambda }^{ar}\left(K_n\right)=\frac{n(n-k-1)}{2}$.

Case 2. k = n−1, $S_{n,n-1}$ is isomorphic to the n-star graph $S_n$. By Corollary 3.1, we have ${\lambda }^{ar}\left(S_{n,n-1}\right)={\lambda }^{ar}\left(S_n\right)=\frac{n!(n-k-1)}{2}$.

Case 3. k = n−2, $S_{n,n-2}$ is isomorphic to the n-dimensional alternating group graph $A{N}_n$. By Theorem 3.3, we have ${\lambda }^{ar}\left(S_{n,n-2}\right)={\lambda }^{ar}\left(A{N}_n\right)=\frac{n!(n-a-1)}{4}$.

Case 4. $2\le k\le n-3$.

First, we prove ${\lambda }^{ar}\left(S_{n,k}\right)\le \frac{n(n-1)(n-2)\cdots (n-k+1)}{2}(n-3)$ by induction on k. For k = 2. Since the set of all cross edges between any two subgraphs $S_{n,k}^i$ and $S_{n,k}^j(i\ne j\in 〈n〉)$ is denoted by $E(i,j)$ with order $|E(i,j)|=\frac{(n-2)!}{\left(n-k\right)!}$, it is clearly that $S_{n,2}$ can be decomposed into n subgraphs $S_{n-1,1}^i$($i\in \{1,2,\dots ,n-1\}$) by deleting $\frac{(n-2)!}{\left(n-k\right)!}\cdot \left(n-1\right)\cdot n\cdot \frac{1}{2}=\frac{n!}{2\left(n-k\right)!}$ cross edges. Since $S_{n-1,1}$ is isomorphic to the complete graph $K_{n-1}$, by Lemma 3.6, we have ${\lambda }^{ar}\left(S_{n,2}\right)\le \frac{n!}{2\left(n-2\right)!}+n\cdot \frac{(n-1)(n-4)}{2}=\frac{n(n-1)}{2}(n-3)$, the desired. When k = 3, it is clearly that $S_{n,3}$ can be decomposed into n subgraphs $S_{n-1,2}^i$($i\in \{1,2,\dots ,n-1\}$) by deleting $\frac{n!}{2\left(n-3\right)!}$ cross edges. Similar to the above method, we have ${\lambda }^{ar}\left(S_{n,3}\right)\le \frac{n!}{2\left(n-3\right)!}+n\cdot \frac{(n-1)(n-2)(n-4)}{2}=\frac{n(n-1)(n-2)}{2}(n-3)$. Then we suppose k=n−4 holds. We have ${\lambda }^{ar}\left(S_{n,n-4}\right)\le \frac{n!}{48}(n-3)$. Now, it suffices to consider when k=n−3. It is clearly that $S_{n,n-3}$ can be decomposed into n subgraphs $S_{n-1,n-4}^i$($i\in \{1,2,\dots ,n-1\}$) by deleting $\frac{n!}{2\cdot 3!}$ cross edges. Similar to the above method, we have ${\lambda }^{ar}\left(S_{n,n-3}\right)=\frac{n!}{2\cdot 3!}+n\cdot {\lambda }^{ar}\left(S_{n-1,n-4}\right)\le \frac{n!}{12}(n-3)$. Thus, we have ${\lambda }^{ar}\left(S_{n,k}\right)\le \frac{n(n-1)(n-2)\cdots (n-k+1)}{2}(n-3)$.

Next, we prove ${\lambda }^{ar}\left(S_{n,k}\right)\ge \frac{n(n-1)(n-2)\cdots (n-k+1)}{2}(n-3)$. Let F be a minimum a-regular edge-cut and suppose that $|F|\le \frac{n(n-1)(n-2)\cdots (n-k+1)}{2}(n-3)-1$. Similar to the above method, we have ${\lambda }^{ar}\left(S_{n,k}\right)\ge \frac{n(n-1)(n-2)\cdots (n-k+1)}{2}(n-3)$. The result is desired.

In summary, ${\lambda }^{ar}\left(S_{n,k}\right)=\{\begin{array}{l}{\displaystyle \frac{n(n-a-1)}{2}},k=1\\ \begin{array}{l}{\displaystyle \frac{n!(n-a-1)}{2}},k=n-1\\ {\displaystyle \frac{n!(n-a-1)}{4}},k=n-2\end{array}\\ {\displaystyle \frac{n(n-1)(n-2)\cdots (n-k+1)}{2}}(n-3),2\le k\le n-3.\end{array}$

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 $Q_n$, $S_n$, $B_n$, ${\mathrm{\Gamma }}_n$ and $A{N}_n$ are shown in Tables 1–4.

Table 1. Comparison of conditional connectivity for $Q_n$.

Network		Component edge	Extra edge	Embedded edge	Regular edge
		connectivity	connectivity	connectivity	connectivity
$Q_n$		$\begin{array}{l}c{\lambda }_2\left(Q_n\right)=n\\ c{\lambda }_3\left(Q_n\right)=2n-1\end{array}$ [19]	$\begin{array}{l}{\lambda }_2\left(Q_n\right)=2n-2\\ {\lambda }_3\left(Q_n\right)=3n-4\end{array}$ [19]	$\begin{array}{l}{\lambda }_2\left(Q_n\right)=4n-8\\ {\lambda }_3\left(Q_n\right)=8n-24\end{array}$ [24]	$2^{n-1}(n-a)$

Table 2. Comparison of conditional connectivity for $S_n$ and $B_n$.

Network		Restricted edge	Embedded edge	Regular edge
		connectivity	connectivity	connectivity
$S_n$		${\lambda }_3\left(S_n\right)=24n-120$ [25]	${\eta }_3\left(S_n\right)=6n-18$ [24]	${\displaystyle \frac{n!(n-a-1)}{2}}$
$B_n$		${\lambda }_3\left(B_n\right)=3n-7$ [6]	${\eta }_3\left(B_n\right)=6n-8$ [24]	${\displaystyle \frac{n!\left(n-a-1\right)}{2}}$

Table 3. Comparison of conditional connectivity for Cayley graphs generated by transposition trees ${\mathrm{\Gamma }}_n$.

Network		Restricted edge	Extra edge	Regular edge
		connectivity	connectivity	connectivity
${\mathrm{\Gamma }}_n$		${\lambda }_2\left({\mathrm{\Gamma }}_n\right)=4n-12$ [38]	${\eta }_2\left({\mathrm{\Gamma }}_n\right)=3n-7$ [35]	${\displaystyle \frac{n!(n-a-1)}{2}}$

Table 4. Comparison of conditional connectivity for alternating group network $A{N}_n$.

Network		Restricted edge	Edge neighbour	Regular edge
		connectivity	connectivity	connectivity
$A{N}_n$		${\lambda }_3\left(A{N}_n\right)=12n-48$ [17]	${\eta }_3\left(A{N}_n\right)=n-2$ [1]	${\displaystyle \frac{n!(n-a-1)}{4}}$

We make comparisons among $Q_n$ for different values of the dimension n by a simulation experiment and illustrate the comparison results in Figure 5. In the simulation experiment, the parameter a in the regular edge connectivity are 2 and 3. As we can see from Figure 5 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 $2^{n-1}$, 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 $S_n$ and $B_n$ for different values of the dimension n by a simulation experiment and illustrate the comparison results in Figure 6. After simulating experiments, we get the same results for BC network, $A{N}_n$ and $S_{n,k}$ (Figure 7). 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.

Figure 5. Illustration of comparisons among the conditional connectivity of $Q_n$ with fixed a.

Figure 6. Illustration of comparisons among the conditional connectivity of $S_n$ and $B_n$.

Figure 7. Illustration of comparisons among the conditional connectivity of Cayley graph and $A{N}_n$.

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

This work was partly supported by the National Natural Science Foundation of China [grant numbers 61977016, 61572010, and 62277010], Natural Science Foundation of Fujian Province, China [grant numbers 2020J01164 and 2017J01738]. This work was also partly supported by the China Scholarship Council [CSC number 202108350054].