On the restricted connectivity of the arrangement graph

Abstract

We derive a general upper bound of the $R_h$ -restricted connectivity for the arrangement graph, namely the minimum cardinality of a vertex set, whose removal disconnects the graph, but every remaining vertex has at least $h ({\ge }0)$ neighbors in the survival graph. We show that this upper bound is exact when $h \in [0, 2]$ and provide an asymptotic lower bound for the cases where $h\ge 3$.

1 Introduction

Because of a rapid and consistent technical progress in networking hardware [20, 31], scalable multi-processor (core) systems have become a reality, where an interprocessor communication enabling network plays a crucial role. Many applications have been found with such systems [1, 3,4,5,6,7,8,9,10,11,12,13, 33], in which hardware and software work in concert. To have an effective system to work with, we are naturally interested in the fault tolerance properties of these network structures, when we seek answers to such questions as how many faulty vertices could disrupt such a structure or disconnect its associated graph in graph theory terms; how disrupted such a structure would become when a certain number of vertices become faulty, thus effectively removed; and even how could we identify exactly which vertices are faulty so that connectivity of such a system can be restored?

Answers to such, and other, fault tolerance-related questions can often be provided in terms of connectivity-related properties of a graph underlying such a network structure. To begin with, the vertex connectivity of a non-complete graph G,  denoted by $\kappa (G),$ refers to the minimum size of a vertex cut $F, F \subset V(G),$ such that G–F is disconnected, where G–F, the survival graph henceforth, is obtained from G by deleting all the vertices in F from G, together with all the edges incident to at least one vertex in F. By convention, $\kappa (K_n)$, the vertex connectivity of a complete graph $K_n$, is defined to be $n-1$. In general, $\kappa (G) \le \delta (G)$, the minimum degree of a vertex in G.

Vertex connectivity certainly provides an answer to the question that how many vertices should be removed to disrupt a network. But it is clear that there is a difference between a disrupted network consisting of a large number of small components and one consisting of a large core together with a small number of vertices not in the core. As a result, a series of attempts have been made to disallow such “forbidden sets” [21], including those containing all the neighbors of any vertex [21, 23, 27], and then characterize the corresponding fault tolerance of a graph as the minimum cardinality of a vertex cut, none forbidden. Such attempts lead to a variety of connectivity-related notions and results that are used to quantify the fault tolerance features of networks, some of which will be discussed in this paper.

Regarding disruptive status of a structure, let G be an r-regular graph where the degree of all the vertices in G is r, G is maximally connected [2] if, when removing a vertex set $F, |F|< r$, the survival graph, G–F, is connected. Such a maximally connected graph is also tightly superconnected [2], when $|F| \le r$, if G–F consists of a connected component, and at most one singleton f. Clearly, when such a vertex f does materialize in G–F, all the neighbors of f are included in F. In other words, the degree of the vertex f in the survival graph is 0, e.g., when all the neighbors of a certain processor in a network become faulty simultaneously. Obviously, when used as an interconnection network, an r-regular tightly superconnected structure is preferable than an r-regular maximally connected graph, as when up to r vertices become faulty, the survival graph, except one vertex, is still connected, thus functioning.

Tight superconnectivity can be regarded as a special case of the $R_h$-restricted connectivity, $h \ge 0$ [27, 38], where every vertex of the survival graph has at least $h ({\ge }0)$ neighbors therein.¹ More specifically, given a connected graph G, $F\ (\subset V(G))$ is an $R_h$ -vertex cut of G, $h \ge 0$, if G–F is disconnected and, for all $v \in V(G) {\setminus } F$, $d_{G-F}(v)$, the degree of v in the survival graph G–F, is at least h. The $R_h$ -restricted connectivity of G, denoted by $\kappa _h(G)$, is the minimum cardinality of $R_h$-vertex cuts of G. Since a complete graph cannot be disconnected by removing vertices, $\kappa _h(K_n)$ is not defined for any h. For a graph G that is not complete, since an $R_h$-vertex cut of G is automatically an $R_{h^{\prime }}$-vertex cut, where $h \ge h^{\prime }$, and $\kappa _h(G)$ is a minimizer, we have $\kappa _{h}(G) \ge \kappa _{h^{\prime }}(G) \ge \kappa _0(G)\ ({=}\kappa (G)),$ for all $h \ge h^{\prime } \ge 1$. Intuitively, the larger its $R_h$-restricted connectivity is, the more fault tolerant a network becomes.

Although the problem of computing $\kappa _h(G)$ for a general graph G seems to be NP-hard, as no polynomial algorithm is known [27, 35], numerous results have been obtained for specific graphs, including the hypercube [21, 29], the k-ary n-cube structure [36]; and both $R_1$- and $R_2$-restricted connectivity results were also derived for the star graph [34]. For the (n, k)-star graph, both $R_1$- and $R_2$-restricted connectivity were obtained in [35], and its general $R_h$-restricted connectivity, for $k \in [2, n-1], h \in [0, n-k],$ was later derived in [28]. This latter result also led to a general result for the star graph, which is isomorphic to an $(n, n-1)$-star graph [18]. On the other hand, although both $R_1$- and $R_2$-restricted connectivities were derived in [38] for the arrangement graph, another well-studied network structures proposed in [19], to the best of our knowledge, no general result to this regard has appeared in the literature. As the main contribution of this paper, we provide a general upper bound, as well as a general, but asymptotic, lower bound, of $R_h$-restricted connectivity for the arrangement graph.

As an important application, this notion of $R_h$-vertex cut of G, also referred to as the g-good-neighbor cut in the literature, has been made use of in deriving the g-good-neighbor diagnosability of a variety of graphs [30, 36], which exposes the maximum number of faulty vertices that can be diagnosed, thus corrected, when each vertex in the survival graph has at least g non-faulty neighbors. Incidentally, this notion of g-good-neighbor diagnosability is more restrictive as compared with that of the conditional diagnosability [26], another well-studied fault tolerance characterization, when $g=1$, in the sense that the conditional cut notion requires that, any vertex, faulty or not, have at least one non-faulty neighbor; while the 1-good-neighbor cut only requires that a non-faulty vertex has at least one non-faulty neighbor. Thus, a conditional faulty cut is immediately a 1-good-neighbor cut, but a 1-good-neighbor faulty set may not be a conditional faulty set. As a result, the 1-good-neighbor diagnosability of a graph is a lower bound of its conditional diagnosability [22].

The rest of this paper proceeds as follows: After reviewing the structure of the arrangement graph and some of its basic properties in the following section, we derive a general upper bound for the $R_h$-connectivity of the arrangement graph in Sect. 3, exact bounds when $h \in [0, 2],$ as well as a general asymptotic lower bound in Sect. 4. Section 5 concludes this paper with some final remarks.

2 The arrangement graph and its partitioning

The arrangement graph was suggested to address the scalability issue as associated with the star graph [1], denoted by $S_n$ in the rest of this paper. The arrangement graph preserves many nice properties of the star graph such as vertex and edge symmetry, hierarchical and recursive structure, and simple shortest path routing. It has also drawn a considerable amount of attention with its various fault tolerance properties [15, 17, 24, 32, 38].

The vertex set of an (n, k)-arrangement graph, denoted by $A_{n, k}, n\ge 2, k \in [1, n),$ is simply the collection of all the k-permutations taken out of $\langle n \rangle \ (=$ $\{1, 2, \ldots , n\}),$ and two vertices are adjacent to each other if and only if they differ in exactly one position.

More specifically, let $P(n, k)=\{p_1\cdots p_k:p_i \in \langle n \rangle \text{ and } p_i \not = p_k \text{ when } i \not =j \},$ then $V(A_{n, k})=P(n, k),$ and $E(A_{n, k})=\{(u, v):u, v \in V(A_{n, k}) \text{ such } \text{ that } \text{ for } \text{ some } i \in \langle k \rangle , u_i \not = v_i \text{ and } \text{ for } \text{ all } j \not =i, u_j=v_j\}.$ $A_{n, k}$ thus contains exactly $n!/(n-k)!$ vertices.

By saying that a symbol s occurring in a permutation $\alpha \ ({=}p_1\cdots p_k),$ denoted by $s \in \alpha ,$ we mean that, for some $j \in \langle k \rangle , p_j = s.$ Given $u \in V(A_{n, k}),$ $u=u_1\cdots u_k,$ we can obtain a vertex $v \in V(A_{n, k})$ such that $(u, v) \in E(A_{n,k})$ by replacing $u_i, i \in \langle k \rangle ,$ a symbol that occurs in u,  with any of the $n-k$ symbols that do not. Thus, $A_{n, k}$ is a $k(n-k)$-regular graph.

Figure 1 shows $A_{4, 2},$ where, e.g., 12 is adjacent to 13, 14, 32, and 42. Both 1 and 2 occur in 12. Clearly, it is a 4-regular graph.

Fig. 1

$A_{4, 2}$

Since $A_{n, 1}$ is isomorphic to a complete graph $K_n,$ $\kappa _h(K_n)$ is not defined for any h,  and the only arrangement graph $A_{2, k}$ is $A_{2, 1},$ an edge, we will thus assume $n \ge 3, k \in [2, n),$ in the rest of this paper. It is also well known [19] that $A_{n,n-1}$ is isomorphic to $S_n$, and $A_{n, n-2}$ is isomorphic to an alternating group graph $AG_n,$ which can also be viewed as a Cayley graph generated by a star-like structure of triangles [14].

We now explore the structure of an arrangement graph $A_{n, k}$ by looking into two of its partitions. One common partition is to group all the vertices of $A_{n, k}$ that share the same symbol in a position, particularly, the last position k. Each group of such vertices, where the same symbol $i\ (\in [1, n])$ occurs in the last position, often denoted by $H_i,$ constitutes an $A_{n-1, k-1}$ graph. Such a partition thus decomposes $A_{n, k}$ into a structured collection of n copies of $A_{n-1, k-1},$ often facilitating proofs of an inductive nature.

As a demonstrating example, in Fig. 1, $H_1=\{21, 31, 41\},$ which induces an $A_{3, 1}.$ The vertex 21 of $H_1$ is adjacent to exactly two vertices outside $H_1$: 23 of $H_3$ and 24 of $H_4$. There are also exactly two edges, e.g., (31, 32) and (41, 42) between $H_1$ and $H_2$. Readers are referred to, e.g., [15, 38], for properties and applications of such a partition.

We now turn to another way of partitioning $A_{n, k},$ when we group all the vertices of $A_{n, k}$ that share every symbol, but the one in a fixed position. In particular, we focus on the partition that group vertices that share the initial $(k-1)$-segments, but not the last symbol in position k. More specifically, for $n \ge 3, k \in [2, n)$, let $\alpha =p_1\cdots p_{k-1}\ (\in P(n, k-1))$, $V_\alpha$ be $\{\alpha p_k:p_k \in \langle n \rangle {\setminus } \{p_i: p_i{ occursin}\alpha \}\}$, and let $G_\alpha$ be the graph induced by $V_\alpha$. The following result characterizes several useful properties of this alternative partition of the arrangement graph, which we need to prove the forthcoming results. We notice that all these properties hold for the general case when the position in question could be any other position, besides k.

Let $u\ ({=}(u_1, \ldots , u_n))$ and $v\ ({=}(v_1, \ldots , v_n))$ be two n-ary binary vectors, by $u \oplus v$, we mean the number of positions where $u_i$ differs from $v_i$.

Lemma 2.1

For $n\ge 3$ and $k \in [2, n)$, let $A_{n, k}$ be an (n, k)-arrangement graph and let $\alpha \in P(n, k-1).$ (1) $G_\alpha$ is a complete graph of order $n-k+1$, denoted by $K_{n-k+1}^\alpha .$ (2) There are $n!/(n-k+1)!$ such disjoint complete graphs. (3) Any vertex of $K_{n-k+1}^\alpha$ is adjacent to exactly one vertex of $(k-1)(n-k)$ other complete graphs $K_{n-k+1}^\beta$ such that $\alpha \oplus \beta =1,$ i.e., $\alpha$ and $\beta$ differ in exactly one position. (4) For any $\alpha , \beta \in P(n, k-1), \alpha \oplus \beta =1,$ there are exactly $n-k$ edges between $K_{n-k+1}^\alpha$ and $K_{n-k+1}^\beta .$

Proof

We start with a proof of the first statement: For a given $\alpha =p_1\cdots p_{k-1},$ let $u, v \in V_\alpha ,$ then $u=\alpha i$ and $v= \alpha j,$ $i \not = j$ and neither i nor j occurs in $\alpha .$ Clearly $u, v \in V(A_{n, k}),$ and $(u, v) \in E(A_{n, k}).$ Since any symbol that does not occur in $\alpha$ can serve as the last symbol in a vertex in $V_\alpha ,$ $|V_\alpha |=n-(k-1).$ Thus, $G_\alpha ,$ the graph induced by $V_\alpha ,$ is a complete graph of order $n-k+1.$

We continue with a proof of the second statement: Each $(k-1)$-permutation leads to such a complete graph, and there are exactly $P(n, k-1)=n!/(n-k+1)!$ such permutations. Moreover, let $u \in V_\alpha$ and $v \in V_\beta , \alpha \not = \beta .$ Clearly, $u \not = v.$

We proceed to prove the third statement: Let $u \in V_\alpha ,$ then, for some i that does not occur in $\alpha ,$ $u=\alpha i.$ Since $G_\alpha$ is a complete graph of order $n-k+1,$ u is adjacent to $n-k$ vertices of $G_\alpha ,$ i.e., $\alpha j, j \in \langle n \rangle {\setminus } \{p: p = i \text{ or } p \text{ occurs } \text{ in } \alpha \}.$ Moreover, let $v=\beta j, \beta \not = \alpha$, if u is adjacent to v,  it must be the case that $\alpha \oplus \beta =1$ and $j=i.$ It is also clear that, for a given $u=\alpha i, \alpha =p_1\cdots p_{k-1},$ to derive a $\beta$ such that $\alpha \oplus \beta =1,$ we can replace each symbol $p_l, l \in \langle k-1 \rangle ,$ with $n-k$ symbols, i.e., everything that does not occur in u,  including i. Therefore, there are exactly $(k-1)(n-k)$ such $(k-1)$-permutations for $\beta ,$ each leading to a vertex $\beta i$ in $V_\beta .$ Finally, just assume $u\ ({=}\alpha i)$ is adjacent to $v_1, v_2 \in V_\beta , \alpha \not = \beta ,$ by the previous discussion, $v_1=\beta i=v_2,$ where $\alpha \oplus \beta =1.$

We now prove the last statement: For any $\alpha , \beta \in P(n, k-1), \alpha \oplus \beta =1,$ and let $(u, v) \in E(A_{n, k}),$ such that $u=\alpha i, v=\beta j.$ Then, by the proof of Item 3, $i=j.$ Since exactly k symbols occur in $\alpha$ and $\beta$ altogether, there are $n-k$ choices for the symbol i. $\square$

For example, in Fig. 1, let $\alpha =1,$ then $V_1=\{12, 13, 14\},$ which induces a $G_1 (\equiv K_3).$ Indeed, there are in total $|P(4, 1)|\ =4$ such $K_3$’s: $\{G_1, G_2, G_3, G_4\},$ all of which are vertex disjoint. Each vertex in any $K_3$ is adjacent to exactly one vertex of two other $K_3$’s. Finally, there are exactly two edges between any pair of $K_3$’s.

3 A general upper bound for the $R_h$-restricted connectivity

Let G be a graph, and let $S \subset V(G),$ we use $N_G(S)$ to refer to the open neighbors of all the vertices of S in G,  excluding those in S. We often omit the subscript G from this notation, and others, when the context is clear.

It is shown in [19, Theorem 12] that the $k(n-k)$-regular $A_{n, k}$ is also $k(n-k)$-connected. Thus, $A_{n, k}$ is maximally connected. Indeed, it is shown in [15, Theorem 3.4], i.e., the forthcoming Theorem 4.1, that, when we remove no more than $(2k-1)(n-k)-2$ vertices, $n\ge 5, k \in [2, n-2],$ the associated survival graph is either connected or it consists of one large connected component and perhaps one singleton. Since $k(n-k) \le (2k-1)(n-k)-2$ when $k \in [2, n-2],$ such a graph $A_{n, k}$ is tightly superconnected. Moreover, as it is mentioned earlier, $A_{n, n-1}$ is isomorphic to $S_n,$ which has also been known to be tightly superconnected [16]. Thus, $A_{n, k}$ is tightly superconnected, for all $n\ge 5, k \in [2, n).$ Finally, $A_{4, 2}$ is not tightly superconnected, but it is easy to check that $A_{3, 2}$ is.

We now proceed to derive a general upper bound of the $R_h$-restricted connectivity of an arrangement graph, i.e., when we remove at most this many vertices from an arrangement graph, every vertex in each component of the associated survival graph has at least h neighbors in such a component.

Theorem 3.1

For $n \ge 3, k \in [2, n),$ $h \in [0, n-k),$ $\kappa _h(A_{n, k}) \le (h+1)[(k-1)(n-k)-1]+n-k+1.$

Proof

Let $\alpha \in P(n, k-1),$ and let $X \subset V(K_{n-k+1}^\alpha )$ such that $|X|=h+1.$ Notice that $h+1=|X| < | V(K_{n-k+1}^\alpha )|=n-k+1,$ which holds when $h < n-k$ by assumption. It is also easy to see that $G_X,$ the graph induced by X,  is isomorphic to $K_{h+1}.$

Let S be the open neighbor set of X,  i.e., all the neighbors of vertices in X,  excluding those in X.² We will show that S is an $R_h$-vertex cut, i.e., $A_{n, k}-S$ is disconnected, and the degree of every vertex in $A_{n,k}-S$ is at least h. This would establish the result.

We first find out the size of S. It is clear that, since $K_{n-k+1}^\alpha$ is complete, every vertex in this graph, other than those in X, is a neighbor of all the vertices in X. In other words, $V\left( K_{n-k+1}^\alpha \right) {\setminus } X \subset S.$ We now consider neighbors of X outside $K_{n-k+1}^\alpha .$ Let $x \in X, x=\alpha i.$ By Item 3 of Lemma 2.1, for each such i,  x is adjacent to exactly one vertex of $(k-1)(n-k)$ other $K_{n-k+1}^\beta$ graphs such that $\alpha \oplus \beta =1.$

It is certainly possible that $x_1\ ({=}\alpha i)$ and $x_2\ ({=}\alpha j), i \not = j,$ are adjacent to $v_1$ and $v_2,$ vertices of some $K_{n-k+1}^\beta .$ But $v_1=\beta i \not = \beta j=v_2.$ Thus, different vertices in X must be adjacent to different vertices in another component.³ Hence,

$$\begin{aligned} |S|= & {} (n-k+1-|X|)+|X|(k-1)(n-k)=(n-k+1)\nonumber \\&+\,|X|[(k-1)(n-k)-1] \nonumber \\= & {} (h+1)[(k-1)(n-k)-1]+n-k+1. \end{aligned}$$

(1)

Since $h < n-k,$ we have that

$$\begin{aligned} |S|+|X|= & {} (n-k+1)+(h+1)(k-1)(n-k)\\< & {} (n-k+1)[(k-1)(n-k)+1]. \end{aligned}$$

We proceed to show that $A_{n, k}-S$ is disconnected by showing that at least one vertex of $A_{n, k}$ is not in $S \cup X.$ Assume that $n \ge 3, k=2,$ then, $|S|+|X|=(n-1)+(h+1)(n-2).$ On the other hand, $A_{n, 2}$ contains exactly $n(n-1)$ vertices. For the inequality $(n-1)+(h+1)(n-2)<n(n-1)$ to hold, we need to show that $h < {(n-1)}^2/(n-2)-1.$ The latter inequality does hold as, by assumption, $h < n-2,$ and, for all $n>1, n-2 < {(n-1)}^2/(n-2)-1.$

When $n \ge 4, k \in [3, n-1],$ $|S|+|X| < (n-2)[(n-2)(n-3)+1].$ But, $A_{n, k}$ contains $n!/(n-k)!$ vertices, which is at least $n(n-1)(n-2),$ when $k \ge 3.$ To ensure $(n-2)[(n-2)(n-3)+1]<n(n-1)(n-2),$ i.e., $[(n-2)(n-3)+1]<n(n-1),$ we only need $4n>7,$ which holds when $n \ge 2.$

Thus, there is at least one vertex, u,  in $A_{n, k},$ which is not in either X or S. Since $A_{n, k}$ is a connected graph, there must be a path connecting u and some vertex, x,  in X. Such a path, by the definition of S,  must include some vertex s in S. As a result, $A_{n, k}-S$ is disconnected.

We still have to show that, for any vertex $u \not \in S,$ its degree is at least h. Let $u \in X,$ since X induces a complete graph $K_{h+1},$ it has at least $h+1$ neighbors in $G_X,$ and none of them are in S,  by definition. We thus proceed to discuss the case when $u \not \in S \cup X\ ({=}V_\alpha ).$

Let $u\ ({=}\beta l) \in K_{n-k+1}^\beta ,$ where $\beta \not = \alpha .$ By Item 3 of Lemma 2.1, u is adjacent to at most one vertex in $K_{n-k+1}^\alpha .$ We consider two cases:

Case 1: Assume that u is adjacent to $v_1 \in K_{n-k+1}^\alpha ,$ we further consider two subcases.

Subcase 1.1: If u is not adjacent to any other vertices in S,  then, since u has $k(n-k)$ neighbors in $A_{n, k},$ it has at least $k(n-k)-1$ neighbors not in S,  which is clearly at least $h\ (\ge 0)$ under the assumptions of this result.

Subcase 1.2: Otherwise, let u be also adjacent to $v_2 \in S {\setminus } V(K_{n-k+1}^\alpha ),$ and let $v_2 \in V(K_{n-k+1}^\gamma ).$

• If $\beta \not = \gamma ,$ let $v_1=\alpha i,$ and $v_2=\gamma j.$ Since $\beta \not = \alpha ,$ and u is adjacent to $v_1,$ $\alpha \oplus \beta =1, i=l.$ Since u is also adjacent to $v_2,$ and $\beta \not = \gamma ,$ we have $\beta \oplus \gamma =1, j=l.$ Since $v_2 \not \in V(K_{n-k+1}^\alpha ),$ $\alpha \not = \gamma ,$ it must be the case that $\alpha \oplus \gamma =2.$ Thus, by Lemma 2.1, no vertex of $K^\alpha _{n-k+1}$ is adjacent to another in $K^\gamma _{n-k+1}.$ On the other hand, $v_2\ (\in V(K^\gamma _{n-k+1}))$ must be adjacent to some vertex $x \in X\ (\subset V(K^\alpha _{n-k+1})),$ since $v_2 \in S.$ This is a contradiction.

• We thus assume that $\beta =\gamma .$ That is to say, if u,  besides having a neighbor in $K_{n-k+1}^\alpha ,$ also has a neighbor $v_2$ in $S {\setminus } K_{n-k+1}^\alpha ,$ then $v_2 \in V(K_{n-k+1}^\beta ).$ Clearly, in this case, besides $v_1 \in S,$ by Item 1 of Lemma 2.1, u can have at most $n-k$ such neighbors in $S \cap V_\beta .$ Since the degree of u is $k(n-k),$ it has a least $k(n-k)-(n-k)-1= (k-1)(n-k)-1 \ge (n-k)-1 \ge h$ ⁴ neighbors in $A_{n, k}-S,$ by assumption.

Case 2: We now assume that $u\ (=\beta l)$ is not adjacent to any vertex in $K_{n-k+1}^\alpha .$ The case that u is not adjacent to any vertex in S can be argued the same way as Subcase 1.1. We further discuss two more subcases.

Subcase 2.1: Just assume that u is adjacent to $v \in S \cap V(K_{n-k+1}^\gamma ),$ $\beta \not = \gamma .$ Thus, by Lemma 2.1, $\beta \oplus \gamma =1$, $v=\gamma l.$ Since $v \in S,$ it is adjacent to some vertex in $X \subset V^\alpha _{n-k+1},$ thus $\alpha \oplus \gamma =1,$ as well. Further assume that a neighbor $u_1$ of u in $K^\beta _{n-k+1},$ $u_1=\beta p,$ is also adjacent to a vertex $x_1\ ({=}\alpha p)$ in X. Then, $\alpha \oplus \beta =1.$ Since $\beta \oplus \gamma =1,$ and $\alpha \not = \gamma ,$ we have to conclude that $\alpha \oplus \gamma =2,$ which is a contradiction.

In other words, if a vertex in $K_{n-k+1}^\beta$ is adjacent to another vertex in $S \cap K_{n-k+1}^\gamma , \gamma \not = \beta$, then no vertex in $K_{n-k+1}^\alpha$ is adjacent to any vertex in $K_{n-k+1}^\beta .$ In particular, no neighbor of u in $K_{n-k+1}^{\beta }$ can be adjacent to any vertex in X,  i.e., no neighbor of u in $K_{n-k+1}^{\beta }$ is in S. Therefore, at least $n-k\ ({>}h)$ neighbors of u in $K_{n-k+1}^\beta$ are not in S.

Subcase 2.2: The only remaining case is that all neighbors of u that fall into S belong to $K_{n-k+1}^\beta$. Since there are at most $n-k$ such vertices, and u has $k(n-k)$ neighbors altogether, at least $(k-1)(n-k)\ ({\ge }h)$ of its neighbors are outside S.

The proof of this result is now completed. $\square$

4 Bounds for the $R_h$-connectivity

In this section, we utilize several increasingly complicated known results to derive the desired lower bounds of the $R_h$-connectivity for the arrangement graph. In general, when a graph (arrangement graph in our context) is r-regular, one wants to examine the structure of the survival graph when r vertices are deleted, the ideal result is for the graph to be tightly superconnected. The next step is to find the maximum number of vertices one can delete so that the survival graph still has at most one vertex that is not in the large component. This is Theorem 4.1. Its case analysis-based proof relies on the fact that arrangement graph is tightly superconnected. One can then find the maximum number of vertices one can delete so that the survival graph still has at most two vertices that are not in the large component. This is Theorem 4.3. Its proof relies on Theorem 4.1, again through case analysis. We note that there are more cases for us to look into, and there are also exceptional cases for us to consider. So it would be very difficult to obtain a general result when we want to find the maximum number of vertices one can delete so that the survival graph still has at most $r-1$ vertices that are not in the large component. As a result, Theorem 4.5 was established as an asymptotic result, proved with a double induction. We remark that this is one of those textbook cases that the statement was carefully set up so that the induction works, that is, weakening the statement will render the proof incorrect. We refer the readers to [15] for details.

As a start, we observe that, when setting $h=0$ in Eq. 1, we have $k(n-k),$ i.e., the connectivity of $A_{n, k}$ [19, Theorem 12]. Thus, this upper bound is tight for the case when $h=0$.

Regarding $\kappa _1(A_{n, k}),$ the following upper bound result is immediate from Theorem 3.1.

Corollary 4.1

For $n \ge 3, k \in [2, n-1],$ $\kappa _1(A_{n, k}) \le (2k-1)(n-k)-1.$

To derive a lower bound result of $\kappa _1(A_{n, k}),$ we notice the following strong connectivity result that provides an upper bound of the size of a vertex cut, when at most this many vertices are removed, the survival graph is either connected or it consists of a large component and at most a singleton.

Theorem 4.1

[15, Theorem 3.4] Let n and k be positive integers, $k \in [2, n-2], n \ge 5,$ and $T \subset V(A_{n, k}),$ such that $|T| \le (2k-1)(n-k)-2.$ Then $A_{n, k}-T$ is either connected or it consists of a large component and a singleton.

An $R_1$-vertex cut, besides disconnecting a graph, leads to a survival graph where every vertex has to have at least a neighbor there, thus, a small component in such a survival graph has to contain at least two vertices. As a result, an $R_1$-vertex cut has to contain at least $(2k-1)(n-k)-2$ plus one vertex.

Corollary 4.2

For $n \ge 5, k \in [2, n-2],$ $\kappa _1(A_{n, k}) \ge (2k-1)(n-k)-1.$

Noticing $n \ge 5$ in the above result, we now address several smaller arrangement graphs. When $n=3,$ since $A_{3, 1}$ is isomorphic to a triangle, i.e., a $K_3,$ for which $R_1$-restricted connectivity is not defined, we only need to consider $A_{3, 2},$ which is isomorphic to a 6-cycle. If we just remove any one of the six vertices, the remaining graph is still connected. In fact, we have to remove two vertices, $u, v, d(u, v)=2,$ to get two components, each an edge, to meet our needs. We notice that Eq. 1 also gives a value of 2 when we set n, k, h to 3, 2, and 1, respectively.

When $n=4,$ we only need to consider $A_{4, 2},$ as shown in Fig. 1. If we remove just four vertices from such a graph, it can be checked that the survival graph is either connected, or it is a collection of two 4-cycles, when we delete 13, 24, 31, and 42. On the other hand, if we remove another one out of the remaining eight vertices, the survival graph consists of one 4-cycle and another length-2 path, consisting of three vertices. Thus, an $R_1$-restrict vertex cut for $A_{4, 2}$ contains at least four vertices, i.e., $\kappa _1(A_{4, 2}) \ge 4.$ We notice that the inequality as contained in the above Corollary 4.2 gives a lower bound of 5 for this case. Thus, this inequality does not hold for the case of $n=4.$

As mentioned earlier, $A_{n, n-2}$ is isomorphic to $AG_n,$ the alternating group graph, and it is shown in [14, Theorem 5] that, for $n \ge 5,$ for every vertex in $AG_n$ to have a degree of at least one in the survival graph, the vertex cut has to contain at least $4n-11$ vertices. This conclusion is certainly consistent with Eq. 1 by setting n, k, h to $n, n-2$ and 1, respectively. When $n=4,$ we come back to the $A_{4, 2}$ case.

We also observe that $A_{n, n-1}$ is isomorphic to $S_n,$ the star graph, and it is shown in [25] that for $n \ge 3, \kappa _1(S_{n}) = 2n-4,$ also consistent with Eq. 1 when we set n, k, h to $n, n-1$ and 1, respectively.

By combining Corollary 4.1, Corollary 4.2, and the above discussion, we have achieved the following exact bound result for $\kappa _1(A_{n, k}).$

Theorem 4.2

For $n \ge 3, n \not = 4, k \in [2, n),$ $\kappa _1(A_{n, k}) = (2k-1)(n-k)-1.$ And $\kappa _1(A_{4, 2}) = \kappa _1(A_{4, 3})\ (=\kappa _1(S_{4}))= 4.$

The above result is the same as that of [38, Theorem 3.3], where $n \ge 4, k \in [3, n).$ Incidentally, $\kappa _1(A_{n, k})$ also gives the edge-connectivity of $A_{n, k}$ [38], as a minimum $R_1(A_{n, k})$ actually separates an edge from its neighbors.

We continue to address the case of $h=2.$ The following result is a special case of Theorem 3.1, when setting $h=2.$

Corollary 4.3

Let $n \ge 3, k \in [2, n-1].$ Then $\kappa _2(A_{n, k}) \le (3k-2)(n-k)-2.$

When seeking a lower bound for $\kappa _2(A_{n, k}),$ we again notice the following strong connectivity result, which provides an upper bound of the size of a vertex cut, when at most this many vertices are removed, the survival graph is either connected or it consists of a large component and small components containing at most two vertices altogether.

Theorem 4.3

[15, Theorem 3.7] Let n and k be positive integers such that $n \ge 8, k \in [2, n-5],$ $T \subset V(A_{n, k}),$ such that $|T| \le (3k-2)(n-k)-4.$ Then $A_{n, k}-T$ is either connected or it consists of a large component and small components with at most two vertices in total unless $k=2$ and $|T|=4n-12,$ in which case $A_{n, k}-T$ could have a large component and a 4-cycle.

By the same token as that for the case of $h=1,$ an $R_2$-vertex cut, besides disconnecting a graph, has to lead to a survival graph where every vertex has at least two neighbors in the survival graph. Thus, a small component in such a survival graph has to contain at least three vertices altogether. As a result, an $R_2$-vertex cut, by Theorem 4.3, has to contain at least $(3k-2)(n-k)-3$ vertices. Nevertheless, it is not the case that every cut that leads to a survival graph where small components contain at least three vertices is a $R_2$-vertex cut. For example, the one that leads to a survival graph consisting of a large component and a length-2 path, (u, v, w),  will not do, since neither u nor w has two neighbors. It is easy to calculate that the neighborhood of such a length-2 path consists of exactly $(3k-2)(n-k)-3$ vertices, as u has $k(n-k)-2$ neighbors, excluding both v and w,  while both v and w have $k(n-k)-1$ neighbors, excluding u. Moreover, both u and v (respectively, u and w) have $n-(k+1)$ common neighbors and, finally, v and w have u as their only common neighbor.

As a result, an $R_2$-vertex cut contains at least $(3k-2)(n-k)-2$ vertices, where each vertex is adjacent to at least two vertices. In the best scenario, the survival graph contains a large component and a triangle (u, v, w, u), and the neighborhood of such a triangle contains exactly $(3k-2)(n-k)-2$ vertices.

When $k=2,$ Corollary 4.3 gives an exact bound of $4n-10,$ which is larger than $4n-12,$ the special case as given in Theorem 4.3. It is also clear that every vertex in a 4-cycle has exactly two neighbors. Observed from another angle, by Corollary 4.3, $\kappa _2(A_{4, 2}) \le 6.$ On the other hand, as discussed earlier, the vertex set $\{13, 24, 31, 42 \}$ is a $R_2$-vertex cut. Thus, $\kappa _2(A_{4, 2}) \le 4.$ Indeed, it is shown in [37] that $\kappa _2(A_{4, 2})=4$; and, for all $n\ge 5,$ $\kappa _2(A_{n, n-2})= 6n -18,$ which is consistent with Eq. 1 by setting n, k, h to $n, n-2$ and 2, respectively, or equivalently, the expression as shown in Corollary 4.3 by setting k to $n-2$.

Furthermore, when setting $k=n-1$ in the expression as shown in Corollary 4.3, we get $\kappa _2(S_{n})\ ({=}3n-7),$ which agrees with $\kappa _2(S_{n, k})\ ({=}n+2k-5), n \ge 4, k \in [2, n-2]$ [35, Theorem 2.2], when setting k to $n-1$; and $\kappa _h(S_{n, k})\ ({=}n+h(k-2)-1), n \ge 4, k \in [2, n-1], h \in [0, n-k],$ [28, Theorem 3.4], when setting h to 2, and k to $n-1.$

The following result summarizes Corollary 4.3 and the above discussion.

Theorem 4.4

For $n \ge 8, \kappa _2(A_{n, 2}) =4n-12;$ and, for $k \in [3, n-5]\cup \{n-2,n-1\},$ $\kappa _2(A_{n, k}) = (3k-2)(n-k)-2.$

The above result agrees with that of [38, Theorem 3.7], which comes with a scope of $n \ge 6, k \in [4, n-2],$ thus more inclusive.

For the general case of $h \ge 3,$ we observe that the upper bound as given in Theorem 3.1 generalizes the results on $\kappa _0(A_{n, k})\ ({=}\kappa (A_{n, k})),$ $\kappa _1(A_{n, k}),$ and $\kappa _2(A_{n, k}),$ by setting h to 0, 1, and 2 in Eq. 1. On the other hand, we need a general lower bound result to establish the validity of such an exact bound. To this regard, the above strong connectivity results, Theorems 4.1 and 4.3, are obtained by making induction in terms of $H_i,$ components obtained by partitioning $A_{n, k}$ into groups of vertices that agree on the symbols in the last position k,  i.e., the first way of partitioning $A_{n, k},$ as discussed in Sect. 2. The proofs of such results get more complicated as the value of h increases, as observed in [15].

As discussed at the beginning of this section, in the following general result, besides n and k,  another variable r was introduced to asymptotically characterize the size of the vertex cut for the general case.

Theorem 4.5

[15, Theorem 4.1] Let n, k, r be positive integers such that $k \in [2, n-2], r \ge 1,$ $T \subset V(A_{n, k}),$ such that $|T| \le \left( r(k-2)+2-\frac{r^2}{2}\right) (n-k).$ Then $A_{n, k}-T$ is either connected or it consists of a large component and small components with at most $r-1$ vertices in total.

If a vertex in a component of the survival graph has to have at least h neighbors in that component, the total number of vertices as contained in that component must be at least $h+1$ vertices. This trivially implies that the small components must have at least $h+1$ vertices altogether. As a result, the number of vertices that an $R_h$-vertex cut contains must be strictly more than the upper bound as given in Theorem 4.5, when setting $r=h+1.$ We thus have the following final result of an asymptotic nature.

Theorem 4.6

Let n, k, h be positive integers such that $n \ge 4, k \in [2, n-2], h \ge 3.$ Then

$$\begin{aligned} \left( (h+1)(k-2)+2-\frac{{(h+1)}^2}{2}\right) (n-k)< \kappa _h(A_{n, k}) \le [(h+1)(k-1)+1](n-k)-h. \end{aligned}$$

We notice a gap of $\left( h+\frac{{(h+1)}^2}{2} \right) (n-k),$ a quadratic function of h,  between the above lower and upper bounds. Such a gap reminds us that, besides the fact that the upper bound as given in Theorem 4.5 is an asymptotic result, such a vertex cut as characterized is not necessarily an $R_h(A_{n, k})$ cut, as discussed when we addressed the $h=2$ case, thus the resulting lower bound cannot be tight.

It is certainly desirable to prove that the general upper bound as given in Theorem 3.1 is indeed also a lower bound of the $R_h$-restricted connectivity, which we have to leave as a conjecture.

We observe that, besides the fact that such an equality does not hold for smaller cases, as shown in both Theorems 4.2 and 4.4, a challenge in proving the general case, as compared with tackling a similar task for the (n, k)-star case [28], is that every vertex in an $H_i$ component in an (n, k)-star graph has at most one vertex outside $H_i,$ thus succumbing to an inductive argument. On the other hand, a vertex in an $H_i$ component of an arrangement graph has exactly $n-k$ neighbors outside $H_i$ [15, Section 2], which could effectively disable an inductive argument: Just consider a vertex $u \in H_i-S_i,$ where S is an $R_h$-vertex cut of $A_{n, k},$ i.e., every vertex in $A_{n, k}-S$ contains at least h neighbors therein; and $S_i=S \cap H_i, i \in [1, n].$ In the special case that u has exactly h neighbors in $A_{n, k}-S,$ it could be the case that all of its $(k-1)(n-k)$ neighbors in $H_i$ are included in $S_i,$ together with $n-k$ neighbors outside $H_i.$ Then, although S is an $R_h$-restricted vertex cut of $A_{n, k},$ all the non-faulty neighbors of a vertex of $H_i-S_i$ are located outside $H_i.$ In other words, $S_i$ could be an $R_0$-restricted vertex cut of $H_i,$ i.e., a mere vertex cut of $H_i.$ Thus, an inductive argument would fail to apply in such a situation.

5 Conclusion

In this paper, we derived a general upper bound, as well as a general, but asymptotic, lower bound, of the $R_h$-restricted connectivity for the arrangement graph, $A_{n, k},$ namely the minimum cardinality of a vertex set, whose removal disconnects the graph, but every remaining vertex has at least h neighbors in the survival graph.

We also showed that such an upper bound is exact when $h=0, 1,$ and 2, with the help of strong connectivity results already established for the arrangement graph. Whether such an agreement extends to the cases when $h \in [3, n-k)$ remains an open problem.