Printer Friendly

The Edge Connectivity of Expanded k-Ary n-Cubes.

1. Introduction and Terminology

Mass data processing and complex problem solving have higher and higher demands for performance of multiprocessor systems. Many multiprocessor systems have interconnection networks (networks for short) as underlying topologies and a network is usually represented by a graph G = (V, E) where nodes (vertices) represent processors and links (edges) represent communication links between processors. The network determines the performance of the system. For the network (graph) G, two vertices u and v of G are said to be connected if there is a (u, v)-path in G. Connection is an equivalence relation on the vertex set V. Thus there is a partition of V into nonempty subsets [V.sub.1], [V.sub.2], ..., [V.sub.[omega]] such that two vertices u and V of G are connected if and only if both u and V belong to the same set [V.sub.i]. The subgraphs G[[V.sub.1]], G[[V.sub.2]], ..., G[[V.sub.[omega]]] are called the components of G. If G has exactly one component, then G is connected; otherwise G is disconnected. In the system where the processors and their communication links to each other are likely to fail, it is important to consider the fault tolerance of the network. The fault tolerance of large networks is usually a measure of the extent to which the network can retain its original nature in the event of a certain number of nodes of failure and/or links failure in the network topology. For a connected network (graph) G = (V, E), its inverse problem is that G - F is disconnected, where F [subset or equal to] V or F [subset or equal to] E. The connectivity or edge connectivity is the minimum number of [absolute value of (F)]. Connectivity plays an important role in measuring the fault tolerance of the network.

Let G = (V, E) be a simple graph. Given a nonempty vertex subset V' of V, the induced subgraph by V' in G, denoted by G[V'], is a graph, whose vertex set is V' and the edge set is the set of all the edges of G with both endpoints in V'. The degree [d.sub.G](v) of a vertex v is the number of edges incident with v. We denote by [delta](G) the minimum degrees of vertices of G. For any vertex v, we define the neighborhood [N.sub.G](v) of v in G to be the set of vertices adjacent to v. If u [member of][N.sub.G](v), then u is called a neighbor or a neighbor vertex of V. Let S [subset or equal to] v. We use [N.sub.G](S) to denote the set [[union].sub.V[member of]S] [N.sub.G](v) \ S. A graph G is said to be k-regular if for any vertex v, [d.sub.G](v) = k. For graph-theoretical terminology and notation not defined here we follow [1]. For a faulty subset S of edges in a connected graph G, S is a k-restricted edge cut if G - S is disconnected and every component of G-S has at least k vertices. If such an edge cut exists, then the k-restricted edge connectivity of G, denoted by [[lambda].sub.k](G), is defined as the cardinality of a minimum k-restricted edge cut. For any positive integer k, let [[xi].sub.k](G) = min{[absolute value of ([X, [bar.X]])] : [absolute value of (X)] = k, G[X] is connected}. For many graphs, it has been shown that [[xi].sub.k](G) is an upper bound on [[xi].sub.k](G) [2-4]. A [[lambda].sub.k]-connected graph G is [[lambda].sub.k]-optimal if [[lambda].sub.k](G) = [[xi].sub.k](G). The following is the definition on super-[[lambda].sub.k] graphs used in our manuscript.

Definition 1 (see [5]). A [[lambda].sub.k]-connected graph G is super k- restricted edge-connected (or super-[[lambda].sub.k] for short) if every minimum k-restricted edge cut of G isolates one connected subgraph of order k.

In the majority of the literature, the 1-restricted edge connectivity of G is called the edge connectivity of G and is denoted by [lambda](G). The 2-restricted edge connectivity of G is called the restricted edge connectivity of G and is denoted by [lambda]'(G). Correspondingly, if G is super 1-restricted edge-connected, then G is super edge-connected. If G is super 2-restricted edge-connected, then G is super restricted edge-connected. The sufficient conditions of super-[[lambda].sub.k] have been studied by several authors; see [6, 7].

The k-ary n-cube has many desirable properties, such as ease of implementation of algorithms and ability to reduce message latency by exploiting communication locality found in many parallel applications [8-10]. Therefore, a number of distributed-memory parallel systems (also known as multicomputers) have been built with a k-ary n-cube forming the underlying topology, such as the Cray T3D[11], the J-machine [12], the iWarp [13], and the IBM Blue Gene [14]. In 2011, Xiang and Stewart [15] proposed the augmented k-ary n-cube. In 2017, Wang et al. [16] proposed the expanded k-ary n-cube X[Q.sup.k.sub.n]. The following is the definition.

Definition 2 (see [16]). The expanded k-ary n-cube, denoted by X[Q.sup.k.sub.n] (n [greater than or equal to] 1 and even k [greater than or equal to] 6), is a graph consisting of [k.sup.n] vertices {[u.sub.0][u.sub.1] ... [u.sub.n-1] : 0 [less than or equal to] [u.sub.i] [less than or equal to] k - 1, 0 [less than or equal to] i [less than or equal to] n - 1}. Two vertices u = [u.sub.0][u.sub.1] ... [u.sub.n-1] and v = [v.sub.0][v.sub.1] ... [v.sub.n-1] are adjacent if and only if there exists an integer j [member of] {0,1, ..., n - 1} such that, for some g [member of] {1, -1, 2, -2}, we have uj = Vj + g (mod k) and [u.sub.i] = [v.sub.i] for all i [member of] {0,1, ..., n - 1} \ {j}.

For clarity of presentation, we omit writing "(mod k)" in similar expressions for the remainder of the paper. In this paper, we prove that (1) X[Q.sup.k.sub.n] is super edge-connected (n [greater than or equal to] 3); (2) the restricted edge connectivity of X[Q.sup.k.sub.n] is 8n - 2 (n [greater than or equal to] 3); (3) X[Q.sup.k.sub.n] is super restricted edge-connected (n [greater than or equal to] 3).

2. The Connectivity of Expanded k-Ary n-Cubes

We can partition X[Q.sup.k.sub.n] into k disjoint subgraphs X[Q.sup.k.sub.n][0], X[Q.sup.k.sub.n][1], ..., X[Q.sup.k.sub.n][k - 1] (abbreviated as XQ[0], XQ[1], ..., XQ[k - 1], if there is no ambiguity), where every vertex u = [u.sub.0][u.sub.1] ... [u.sub.n-1] [member of] V(X[Q.sup.k.sub.n]) has a fixed integer i in the last position [u.sub.n-1] for i [member of] {0,1, ..., k - 1}. Let u [member of] V(XQ[i]). Then N(u) \ V(XQ[i]) is said to be outside neighbor vertices of u.

Proposition 3 (see [16]). Each XQ[i] is isomorphic to X[Q.sup.k.sub.n-1] for 0 [less than or equal to] i [less than or equal to] k - 1.

Proposition 4. The expanded k-ary n-cube is the Cartesian product of n expanded k-ary 1-cubes, i.e., [mathematical expression not reproducible].

Proof. We prove [mathematical expression not reproducible] by the induction on n. Now define a bijection from V(X[Q.sup.k.sub.2]) to V(X[Q.sup.k.sub.1] [cross product] X[Q.sup.k.sub.1]) given by

[phi] : [u.sub.1][u.sub.0] [right arrow] ([u.sub.1][u.sub.0]). (1)

Note [absolute value of (V(X[Q.sup.k.sub.2]))] = [absolute value of (V(X[Q.sup.k.sub.1] [cross product] X[Q.sup.k.sub.1]))] = [k.sup.2]. Let uv [member of] E(X[Q.sup.k.sub.2]) with u = [u.sub.1][u.sub.0] and v = [v.sub.1][v.sub.0]. Then (1), if [u.sub.1] = [v.sub.1], [u.sub.0] = [v.sub.0] + g (mod k) for g [member of] {1, -1, 2, -2}; (2), if [u.sub.0] = [v.sub.0], [u.sub.1] = [v.sub.1] + g (mod k) for g [member of] {1, -1, 2, -2}. Suppose that [u.sub.1] = [v.sub.1], [u.sub.0] = [v.sub.0] + g. Then [u.sub.0][v.sub.0] [member of] E(X[Q.sup.k.sub.1]). By the definition of X[Q.sup.k.sub.1] [cross product] X[Q.sup.k.sub.1], uv [member of] E(X[Q.sup.k.sub.1] [cross product] X[Q.sup.k.sub.1])). Suppose that [u.sub.0] = [v.sub.0], [u.sub.1] = [v.sub.1] + g. Similarly, uv [member of] E(X[Q.sup.k.sub.1] [cross product] X[Q.sup.k.sub.1])).

Conversely, let uV [member of] E(X[Q.sup.k.sub.1] [cross product] X[Q.sup.k.sub.1])) with u = ([u.sub.1][u.sub.0]) and V = ([v.sub.1][v.sub.0]). Then [u.sub.1] = [v.sub.1], [u.sub.0][v.sub.0] [member of] E(X[Q.sup.k.sub.1]) or [u.sub.0] = [v.sub.0], [u.sub.1][v.sub.1] [member of] E(X[Q.sup.k.sub.1]). Suppose that [u.sub.1] = [v.sub.1] and [u.sub.0][v.sub.0] [member of] E(X[Q.sup.k.sub.1]). By the definition of X[Q.sup.k.sub.1], [u.sub.0] = [v.sub.0] + g (mod k) for g [member of] {1, -1, 2, -2}. By the definition of X[Q.sup.k.sub.2], uv [member of] E([Q.sup.k.sub.2]). Suppose that [u.sub.0] = [v.sub.0] and [u.sub.1][v.sub.1] [member of] E(X[Q.sup.k.sub.1]). Similarly, uv [member of] E([Q.sup.k.sub.2]). This implies that the result is true for n = 2. Assume that the result holds for n = m - 1, i.e., [mathematical expression not reproducible] form [greater than or equal to] 3.

Then [mathematical expression not reproducible]. We will prove that X[Q.sup.k.sub.m] = X[Q.sup.k.sub.1] [cross product] X[Q.sup.k.sub.m-1]. Now define a bijection from V(X[Q.sup.k.sub.m]) to V(X[Q.sup.k.sub.1] [cross product] X[Q.sup.k.sub.m-1]) given by

[phi] : [u.sub.m-1][u.sub.m-2] ... [u.sub.0] [right arrow] ([u.sub.m-1], ([u.sub.m-2] ... [u.sub.0])). (2)

Note [absolute value of (V(X[Q.sup.k.sub.m]))] = [absolute value of (V(X[Q.sup.k.sub.1] [cross product] X[Q.sup.k.sub.m-1]))] = [k.sup.m]. Let uv [member of] E(X[Q.sup.k.sub.m]) with u = [u.sub.m-1][u.sub.m-2] ... [u.sub.0], v = [v.sub.m-1][v.sub.m-2] ... [v.sub.0], u' = [u.sub.m-2] ... [u.sub.0], and v'[v.sub.m-2] ... [v.sub.0],

By Proposition 3, each X[Q.sup.k.sub.m][i] is isomorphic to X[Q.sup.k.sub.m-1] (i in the last position [u.sub.m-1]). Suppose that uv [member of] E(X[Q.sup.k.sub.m][i]). Then [u.sub.m-1] = [v.sub.m-1] = i. By the definition of X[Q.sup.k.sub.1] [cross product] X[Q.sup.k.sub.m-1], uv [member of] E(X[Q.sup.k.sub.1] [cross product] X[Q.sup.k.sub.m-1]). Suppose that uV [member of] E(X[Q.sup.k.sub.m]) [[summation].sup.k-1.sub.i=0] E(X[Q.sup.k.sub.m][i]). Then, by the definition of X[Q.sup.k.sub.m][i], [u.sub.m-1] = [v.sub.m-1] + g and [u.sub.i] = [v.sub.i] for i [member of] {0,1, ..., m - 2} and g [member of] {1, -1, 2, -2}. Therefore, [u.sub.m-1][v.sub.m-1] [member of] E(X[Q.sup.k.sub.1]) and [u.sub.i] = [v.sub.i] for i [member of] {0, 1, ..., m - 2}. By the definition of X[Q.sup.k] 1 [cross product] X[Q.sup.k.sub.m-1] and uv [member of] E(X[Q.sup.k.sub.1] [cross product] X[Q.sup.k.sub.m-1]).

Conversely, let uv [member of] E(X[Q.sup.k.sub.1] [cross product] X[Q.sup.k.sub.m-1])). Suppose that [u.sub.m-1] = [v.sub.m-1] and u'Vv [member of] E(X[Q.sup.k.sub.m-1])). By the definition of X[Q.sup.k.sub.m-1], there exists an integer j [member of] {0, 1, ..., m - 2} such that [u.sub.j] = [v.sub.j] + g (mod k) and [u.sub.i] = [v.sub.i], for i [member of] {0,1, ..., m - 2}\{j} and g [member of] {1, -1, 2, -2}. Note that [u.sub.m-1] = [v.sub.m-1]. By the definition of X[Q.sup.k.sub.m], uv [member of] E(X[Q.sup.k.sub.m]). Suppose that [u.sub.m-1][v.sub.m-1] [member of] E(X[Q.sup.k.sub.1]) and u' = v'. By the definition of X[Q.sup.k.sub.1], [u.sub.i] = [v.sub.i] + g. Note that u' = v'. By the definition of X[Q.sup.k.sub.m], uv [member of] E(X[Q.sup.k.sub.m]).

The automorphism group of a graph G is transitive if there exists an automorphism [phi] to any pair u, v of vertices in G such that [phi](u) = V. In this case, G is called vertex transitive.

Proposition 5 (see [16]). X[Q.sup.k.sub.n] is 4n-regular, vertex transitive.

Proposition 6 (see [16]). Let u [member of] V(XQ[i]). Then four outside neighbor vertices of u are in four different XQ[j]'s.

Theorem 7 (see [16]). Let X[Q.sup.k.sub.n] be the expanded k-ary n-cube with n [greater than or equal to] 1 and even k [greater than or equal to] 6. Then the connectivity [kappa](X[Q.sup.k.sub.n]) = 4n.

Theorem 8 (see [1]). Let G be a connected graph. Then [kappa](G) [less than or equal to] [lambda](G) [less than or equal to] [delta](G).

By Proposition 5 and Theorems 7 and 8, we have the following corollary.

Corollary 9. [lambda](X[Q.sup.k.sub.n]) = 4n.

Theorem10. Let X[Q.sup.k.sub.n] be the expanded k-ary n-cube with n [greater than or equal to] 3 and even k [greater than or equal to] 6. Then X[Q.sup.k.sub.n] is super edge-connected.

Proof. By Corollary 9, [lambda](X[Q.sup.k.sub.n]) = 4n. Let F [subset or equal to] E(X[Q.sup.k.sub.n]) with [absolute value of (F)] = 4n be any minimum edge cut of X[Q.sup.k.sub.n]. We can partition X[Q.sup.k.sub.n] into k disjoint subgraphs XQ[0], XQ[1], ..., XQ[k - 1]. By Proposition 3, each XQ[i] is isomorphic to X[Q.sup.k.sub.n-1] for 0 [less than or equal to] i [less than or equal to] k - 1. Let [F.sub.i] = F [intersection] E(XQ[i]) for i [member of] {0, 1, 2, ..., k - 1} with [absolute value of ([F.sub.0])] = max{[absolute value of ([F.sub.i])] : 0 [less than or equal to] i [less than or equal to] k - 1}. Let [F.sup.n-1] = F [intersection] (E(X[Q.sup.k.sub.m]) \[[summation].sup.k-1.sub.i=0] E(X[Q.sup.k.sub.m][i])). Then F = [F.sup.n-1] [union] [F.sub.0] [union] ... [union] [F.sub.k-1]. Since n [greater than or equal to] 3, [k.sup.n-1] > 4n holds, we consider the following cases.

Case 1 ([absolute value of ([F.sub.0])] [less than or equal to] 4n - 5). Since [absolute value of ([F.sub.0])] = max{[absolute value of ([F.sub.i])] : 0 [less than or equal to] i [less than or equal to] k - 1}, [absolute value of ([F.sub.i])] [less than or equal to] 4n - 5. By Corollary 9, XQ[i] - [F.sub.i] is connected. Since [k.sup.n-1] > 4n and there is a complete matching between XQ[i] and XQ[i + 1] for i [member of] {0,1, ..., k - 2}, X[Q.sup.k.sub.n] - F is connected; a contradiction to that F is an edge cut of X[Q.sup.k.sub.n].

Case 2 ([absolute value of ([F.sub.0])] = 4n - 4). Since n [greater than or equal to] 3, 8n - 8 > 4n holds hence there is only one [F.sub.0] such that [absolute value of ([F.sub.0])] = 4n - 4. Therefore, [absolute value of ([F.sub.i])] [less than or equal to] 4n - 5 for i [member of] {1, ..., k - 1}. By Corollary 9, XQ[i] - [F.sub.i] is connected for i [member of] {1, ..., k - 1}. Since [k.sup.n-1] > 4n and there is a complete matching between XQ[i] and XQ[i + 1] for i [member of] {0,1, ..., k - 2}, X[Q.sup.k.sub.n] [[[union].sup.k-1.sub.i=1] V(XQ[i] - [F.sub.i])] is connected.

Case 2.1 (XQ[0] - [F.sub.0] is connected). Since there is a complete matching between XQ[i] and XQ[i +1] for i [member of] {0,1, ..., k - 2}, X[Q.sup.k.sub.n] - F is connected; a contradiction to that F is an edge cut of X[Q.sup.k.sub.n].

Case 2.2 (XQ[0] - [F.sub.0] is not connected). Since [absolute value of ([F.sub.0])] = 4n - 4 and [absolute value of (F)] = 4n, [absolute value of ([F.sup.n-1])] [less than or equal to] 4 holds. Let [absolute value of ([F.sup.n-1])] [less than or equal to] 3. By Proposition 6, X[Q.sup.k.sub.n] - F is connected; a contradiction to that F is an edge cut of X[Q.sup.k.sub.n]. Let [absolute value of ([F.sup.n-1])] = 4. Let [B.sub.1], ..., [B.sub.j] (j [greater than or equal to] 2) be the components of XQ[0] - [F.sub.0]. Suppose [absolute value of (V([B.sub.i]))] [greater than or equal to] 2 for i = 1, ..., j. By Proposition 6, [absolute value of (V([B.sub.i]) [intersection] ([[union].sup.k-1.sub.i=1] V(XQ[i]))] [greater than or equal to] 8. Since [absolute value of ([F.sup.n-1])] =4, X[Q.sup.k.sub.n] - F is connected, a contradiction to that F is an edge cut of X[Q.sup.k.sub.n]. Therefore, there is a [B.sub.i] such that [absolute value of ([B.sub.i])] = 1. Let V([B.sub.i]) = {b}. Since dXQ[0](b) = 4n - 4 = [absolute value of ([F.sub.0])], there is only a [B.sub.i] such that [absolute value of ([B.sub.i])] = 1. If b is incident with each of [F.sub.0], then X[Q.sup.k.sub.n] - F has two components, one of which is an isolated vertex. If b is not incident with each of [F.sub.0], then X[Q.sup.k.sub.n] - F is connected; a contradiction to that F is an edge cut of X[Q.sup.k.sub.n].

Case 3 (4n - 3 [less than or equal to] [absolute value of ([F.sub.0])] [less than or equal to] 4n). In this case, [absolute value of ([F.sub.n-1])] [less than or equal to] 3 and X[Q.sup.k.sub.n] [[[union].sup.k-1.sub.i=1] V(XQ[i] - [F.sub.i])] is connected. By Proposition 6, X[Q.sup.k.sub.n] - F is connected, a contradiction to that F is a edge cut of X[Q.sup.k.sub.n].

By Cases 1-3, X[Q.sup.k.sub.n] is super edge-connected.

Lemma 11. Let X[Q.sup.k.sub.n] be the expanded k-ary n-cube with n [greater than or equal to] 3 and even k [greater than or equal to] 6. Then [lambda]'(X[Q.sup.k.sub.n]) [less than or equal to] 8n - 2.

Proof. Let [mathematical expression not reproducible]. Then u is adjacent to v and u, v [member of] V(XQ[0]). Let E' = [{u, v}, [bar.{u, v}]]. Then [absolute value of (E')] = 8n - 2 and E' [intersection] E(XQ[i]) = 0 for i [member of] {1, ..., k - 1}. Therefore, X[Q.sup.k.sub.n] [[[union].sup.k-1.sub.i=1] V(XQ[i] - E')] is connected. Let x [member of] V(XQ[0]) \ {u, v}. Then [{x}, [bar.{x}]] [intersection] E' = 0. Therefore, X[Q.sup.k.sub.n] [{x}[union] ([[union].sup.k-1.sub.i=1] V(XQ[i]-E'))] is connected and hence X [Q.sup.k.sub.n] - F has two components [G.sub.1] ([absolute value of (V([G.sub.1]))] = 2) and [G.sub.2] ([absolute value of (V([G.sub.1]))] [greater than or equal to] 2). By the definition of [lambda]', [lambda]'(X[Q.sup.k.sub.n]) [less than or equal to] 8n - 2.

Proposition 12. Let X[Q.sup.k.sub.1] be the expanded k-ary 1-cube with even k [greater than or equal to] 6, and let F [subset or equal to] E(X[Q.sup.k.sub.1]) with [absolute value of (F)] [less than or equal to] 5. If X[Q.sup.k.sub.1] - F is disconnected, then X[Q.sup.k.sub.1] - F has two components, one of which is an isolated vertex.

Proof. If [absolute value of (F)] [less than or equal to] 3, by Corollary 9, then X[Q.sup.k.sub.2] - F is connected, a contradiction. Let [absolute value of (F)] = 4. By Proposition 5, X[Q.sup.k.sub.1] is 4-regular. Therefore, there is one F such that X[Q.sup.k.sub.1] - F has two components, one of which is an isolated vertex. Let [absolute value of (F)] = 5. Suppose that X[Q.sup.k.sub.1] - F has two or more components which have order at least 2. Choose a component A of X[Q.sup.k.sub.1] - F with [absolute value of (V(A))] [greater than or equal to] 2 so that [absolute value of (V(A))] is as small as possible. Then 2 [less than or equal to] [absolute value of (V(A))] [less than or equal to] k/2. In view of Proposition 5, we may assume that V(A) = [[union].sub.1[less than or equal to]i[less than or equal to]p] {[m.sub.i], [m.sub.i] + 1, ..., [m.sub.i] + [h.sub.i] - 1} and {1, ..., k - 1} \ V(A) = [[union].sub.1[less than or equal to]i[less than or equal to]p] {[m.sub.i] + [h.sub.i], [m.sub.i] + [h.sub.i] + 1, ..., [m.sub.i] + 1 - 1}, where p [greater than or equal to] 1 and 0 = [m.sub.1] < [m.sub.1] + [h.sub.1] < [m.sub.2] < [m.sub.2] + [h.sub.2] < ... < [m.sub.p] < [m.sub.p] + [h.sub.p] < [m.sub.p+1] = k. Then [absolute value of (V(A))] = [h.sub.1] + [h.sub.2] + ... + [h.sub.p] and [absolute value of ({0, 1, ..., k - 1} \ V(A))] = ([m.sub.2] - ([m.sub.1] + [h.sub.1])) + ([m.sub.3] - ([m.sub.2] + [h.sub.2])) + ... + (k - ([m.sub.p] + [h.sub.p])). If p [greater than or equal to] 3, then the edge set {{[m.sub.1] + [h.sub.1] - 1, [m.sub.1] + [h.sub.1]}, {[m.sub.2] - 1, [m.sub.2]}, {[m.sub.2] + [h.sub.2] - 1, [m.sub.2] + [h.sub.2]}, {[m.sub.3] - 1, [m.sub.3]}, {[m.sub.3] + [h.sub.3] - 1, [m.sub.3] + [h.sub.3]}, {[m.sub.4] - 1, [m.sub.4]}} [subset or equal to] F (in the case where p = 3, we take {[m.sub.4] - 1, [m.sub.4] } = {k - 1, 0}), and hence [absolute value of (F)] [greater than or equal to] 6, a contradiction to that F = 5. Thus 1 [less than or equal to] p [less than or equal to] 2. Suppose that p = 2. Since [absolute value of ({1, ..., k - 1} \V(A))] [greater than or equal to] 3, we have [m.sup.2] - [h.sup.1] [greater than or equal to] 2 or k - ([m.sup.2] + [h.sup.2]) [greater than or equal to] 2. We may assume [m.sup.2] - [h.sup.1] [greater than or equal to] 2. Then [h.sup.1] + 1, [m.sup.2] - 2 [member of] {1, ..., k - 1} \ V(A), which implies {{[h.sup.1] - 1, [h.sup.1]}, {[h.sup.1] - 1, [h.sup.1] + 1}, {[m.sup.2] - 2, [m.sup.2]}, {[m.sup.2] - 1, [m.sup.2]}, {[m.sup.2] + [h.sup.2] - 1, [m.sup.2] + [h.sup.2]}, {k - 1, 0}} [subset or equal to] F, and hence [absolute value of (F)] [greater than or equal to] 6, a contradiction to that F = 5. Thus p = 1. Since [absolute value of ({1, ..., k - 1} V(A))] [greater than or equal to] [absolute value of (V(A))] [greater than or equal to] 2, it follows that [h.sub.1] [greater than or equal to] 2 and k - [h.sub.1] [greater than or equal to] 2. Consequently 1, [h.sub.1] - 2 [member of] V(A) and [h.sub.1] + 1, k - 2 [member of] {1, ..., k - 1}\V(A), which implies {{[h.sub.1] - 2, [h.sub.1]}, {[h.sub.1] - 1, [h.sub.1]}, {[h.sub.1] - 1, [h.sub.1] + 1}, {k - 2, 0}, {k - 1, 0}, {k - 1, 1}} [subset or equal to] F. Therefore [absolute value of (F)] [greater than or equal to] 6, a contradiction to that F = 5 and hence X[Q.sup.k.sub.1] - F has two components, one of which is an isolated vertex.

Proposition 13. Let X[Q.sup.k.sub.1] be the expanded k-ary 1-cube with even k [greater than or equal to] 6, and let F [subset or equal to] E(X[Q.sup.k.sub.1]) be a minimum 2-restricted edge cut of X[Q.sup.k.sub.1]. Then [absolute value of (F)] = 6.

Proof. By Proposition 12, [absolute value of (F)] [greater than or equal to] 6. Let [{0, 1}, [bar.{0, 1}]]. Then [{0, 1}, [bar.{0, 1}]] is a 2-restricted edge cut of X[Q.sup.k.sub.1] and [absolute value of ([{0, 1}, [bar.{0, 1}]])] = 6. Therefore, [absolute value of (F)] = 6.

Proposition 14. Let X[Q.sup.k.sub.2] be the expanded k-ary 2-cube with even k [greater than or equal to] 6, and let F [subset or equal to] E(X[Q.sup.k.sub.2]) with [absolute value of (F)] [less than or equal to] 13. If X[Q.sup.k.sub.2] - F is disconnected, then X[Q.sup.k.sub.2] - F has two components, one of which is an isolated vertex.

Proof. We can partition X[Q.sup.k.sub.2] into k disjoint subgraphs X[Q.sup.k.sub.2][0], X[Q.sup.k.sub.2][1], ..., X[Q.sup.k.sub.2][k - 1] (abbreviated as XQ[0], XQ[1], ..., XQ[k - 1], if there is no ambiguity), where every vertex [u.sub.0][u.sub.1] [member of] V(X[Q.sup.k.sub.2]) has a fixed integer i in the last position [u.sub.1] for i [member of] {0,1, ..., k - 1}. By Proposition 3, each XQ[i] is isomorphic to X[Q.sup.k.sub.n-1] for 0 [less than or equal to] i [less than or equal to] k - 1. By Corollary 9, [lambda](XQ[i]) = 4. Let [F.sub.i] = F [intersection] V(XQ[i]) for i [member of] {0, 1, 2, ..., k - 1} with [absolute value of ([F.sub.0])] = max{[absolute value of ([F.sub.i])] : 0 [less than or equal to] i [less than or equal to] k - 1}. Let [F.sup.n-1] = F [intersection] (E(X[Q.sup.k.sub.2])\[[summation].sup.k-1.sub.i=0] E(X[Q.sup.k.sub.2][i])). Then F = [F.sup.n-1] [union] [F.sub.0] [union]...[union] [F.sub.k-1]. We consider the following cases.

Case 1 ([absolute value of ([F.sub.0])] [less than or equal to] 3). Since [absolute value of ([F.sub.0])] = max{[absolute value of ([F.sub.i])] : 0 [less than or equal to] i [less than or equal to] k - 1}, [absolute value of ([F.sub.i])] [less than or equal to] 3. By Corollary 9, XQ[i] - F is connected. By Proposition 6 and 13 < 24, X[Q.sup.k.sub.2] - F is connected, a contradiction to that F is a cut of X[Q.sup.k.sub.2].

Case 2 ([absolute value of ([F.sub.0])] = 4). Since [absolute value of ([F.sub.0])] = max{[absolute value of ([F.sub.i])] : 0 [less than or equal to] i [less than or equal to] k - 1}, [absolute value of ([F.sub.i])] [less than or equal to] 4. Since [absolute value of ([F.sub.1])] + ... + |F5| [less than or equal to] 9, there are at most three [F.sub.i]'s such that [absolute value of ([F.sub.i])] = 4 for i [member of] {1, 2 ..., k - 1}.

Case 2.1 ([absolute value of ([F.sub.0])] = 4 and [absolute value of ([F.sub.i])] [less than or equal to] 3 for i [member of] {1,2 ..., k - 1}). By Corollary 9, XQ[i] - [F.sub.i] is connected for i [member of] {1,2 ..., k - 1}. By Proposition 6 and 13 < 24, X[Q.sup.k.sub.2][V(XQ[1] - [F.sub.1]) [union] ... [union] V(XQ[k - 1] - [F.sub.k-1])] is connected. By Theorem 10, XQ[0] - [F.sub.0] is connected or XQ[0] - [F.sub.0] has two components, one of which is an isolated vertex. Since 13 < 20, X[Q.sup.k.sub.2] - F is connected (a contradiction) or X[Q.sup.k.sub.2] - F has two components, one of which is an isolated vertex.

Case 2.2 ([absolute value of ([F.sub.0])] = 4, |[F.sub.i0]| = 4 and [absolute value of ([F.sub.i])] [less than or equal to] 3 for i [member of] {1, 2 ..., k-1}\ {[i.sub.0]}). In this case, [absolute value of ([F.sup.n-1])] [less than or equal to] 5. Similarly to Case 2.1, X[Q.sup.k.sub.2] - F is connected (a contradiction) or X[Q.sup.k.sub.2] - F has two components, one of which is an isolated vertex.

Case 2.3 [mathematical expression not reproducible] and [absolute value of ([F.sub.i])] [less than or equal to] 1 for i [member of] {1,2 ..., k - 1} \ {[i.sub.0], [j.sub.0]}). In this case, [absolute value of ([F.sup.n-1])] [less than or equal to] 1. Similarly to Case 2.1, X[Q.sup.k.sub.2] - F is connected, a contradiction.

Case 3 ([absolute value of ([F.sub.0])] = 5). Since [absolute value of ([F.sub.0])] = max{[absolute value of ([F.sub.i])] : 0 [less than or equal to] i [less than or equal to] k - 1}, [absolute value of ([F.sub.i])] [less than or equal to] 5. Since [absolute value of ([F.sub.1])] + ... + [absolute value of ([F.sub.5])] [less than or equal to] 8, there are at most two [F.sub.i]'s such that [absolute value of ([F.sub.i])] = 4 for i [member of] {1, 2 ..., k - 1}.

Case 3.1 ([absolute value of ([F.sub.0])] = 5 and [absolute value of ([F.sub.i])] [less than or equal to] 3 for i [member of] {1, 2 ..., k - 1}). By Corollary 9, XQ[i] - [F.sub.i] is connected for i [member of] {1, 2 ..., k - 1}. By Proposition 6 and 13 < 24, X[Q.sup.k.sub.2] [V(XQ[1] - [F.sup.1]) [union] ... [union] V(XQ[k - 1] - [F.sub.k-1])] is connected. By Proposition 12, XQ[0] - [F.sub.0] is connected or X[Q.sup.k.sub.2] - F has two components, one of which is an isolated vertex. Since 13 < 20, X[Q.sup.k.sub.2] - F is connected (a contradiction) or X[Q.sup.k.sub.2] - F has two components, one of which is an isolated vertex.

Case 3.2 [mathematical expression not reproducible] and [absolute value of ([F.sub.i])] [less than or equal to] 3 for i [member of] {1, 2 ..., k-1}\ {[i.sub.0]}). In this case, [absolute value of ([F.sup.n-1])] [less than or equal to] 4. Similarly to Case 3.1, X[Q.sup.k.sub.2] - F is connected (a contradiction) or X[Q.sup.k.sub.2] - F has two components, one of which is an isolated vertex.

Case 3.3 ([absolute value of ([F.sub.0])] = 5, [mathematical expression not reproducible] and [absolute value of ([F.sub.i])] [less than or equal to] 3 for i [member of] {1,2 ..., k - 1}\ {[i.sub.0]}). In this case, [absolute value of ([F.sub.n-1])] [less than or equal to] 3. By Proposition 12, XQ[0] - [F.sub.0] is connected or X[Q.sup.k.sub.2] - F has two components, one of which is an isolated vertex. Therefore, X[Q.sup.k.sub.2] - F is connected, a contradiction.

Case 4 (6 [less than or equal to] [absolute value of ([F.sub.0])] [less than or equal to] 13). In this case, [absolute value of ([F.sup.n-1])] [less than or equal to] 7 and [absolute value of ([F.sub.1])] + ... + [absolute value of ([F.sub.k-1])] [less than or equal to] 7. Therefore, XQ[0] - [F.sub.0] is connected (a contradiction) or X[Q.sup.k.sub.2] - F has two components, one of which is an isolated vertex.

Proposition 15. Let X[Q.sup.k.sub.n] be the expanded k-ary n-cube with even k [greater than or equal to] 6, and let F [subset or equal to] E(X[Q.sup.k.sub.n]) with [absolute value of (F)] [less than or equal to] 8n - 3. If X[Q.sup.k.sub.n] - F is disconnected, then X[Q.sup.k.sub.n] - F has two components, one of which is an isolated vertex.

Proof. We can partition X[Q.sup.k.sub.n] into k disjoint subgraphs X[Q.sup.k.sub.n][0], X[Q.sup.k.sub.n][1], ..., X[Q.sup.k.sub.n][k - 1] (abbreviated as XQ[0], XQ[1], ..., XQ[k - 1], if there is no ambiguity), where every vertex [u.sub.0][u.sub.1] ...[u.sub.n-1] [member of] V(X[Q.sup.k.sub.n]) has a fixed integer i in the last position [u.sub.n-1] for i [member of] {0, 1, ..., k - 1}. By Proposition 3, each XQ[i] is isomorphic to X[Q.sup.k.sub.n-1] for 0 [less than or equal to] i [less than or equal to] k - 1. Let F [subset or equal to] E(X[Q.sup.k.sub.n]) with [absolute value of (F)] [less than or equal to] 8n - 3 and let X[Q.sup.k.sub.n] - F is disconnected. Let [F.sub.i] = F [intersection] E(XQ[i]) for i [member of] {0,1, 2, ..., k - 1} with [absolute value of ([F.sub.0])] = max{[absolute value of ([F.sub.i])] : 0 [less than or equal to] i [less than or equal to] k - 1}. Let [F.sup.n-1] = F [intersection] (E(X[Q.sup.k.sub.n]) [[summation].sup.k-1.sub.i=0] E(X[Q.sup.k.sub.n][i])). When n = 2, the result holds by Proposition 14. We proceed by induction on n. Our induction hypothesis is that X[Q.sup.k.sub.n-1] - F has two components, one of which is an isolated vertex for [absolute value of (F)] [less than or equal to] 8n - 11 and n [greater than or equal to] 3. By Proposition 3, each XQ[i] is isomorphic to X[Q.sup.k.sub.n-1] for 0 [less than or equal to] i [less than or equal to] k - 1. We consider the following cases.

Case 1 ([absolute value of ([F.sub.0])] [less than or equal to] 4n - 5). Since [absolute value of ([F.sub.0])] = max{[absolute value of ([F.sub.i])] : 0 [less than or equal to] i [less than or equal to] k - 1}, [absolute value of ([F.sub.i])] [less than or equal to] 4n - 5 for i [member of] {1, 2, ..., k - 1}. By Corollary 9, XQ[i] - F is connected for i [member of] {0,1, ..., k - 1}. Since [k.sup.n-1] > 8n - 13 and there is a complete matching between XQ[i] and XQ[i + 1], for i [member of] {0, 1, ..., k -2}, X[Q.sup.k.sub.n] - F is connected; a contradiction to that F is a cut of X[Q.sup.k.sub.n].

Case 2 (4n - 4 [less than or equal to] [absolute value of ([F.sub.0])] [less than or equal to] 4n + 1). In this case, [absolute value of ([F.sub.1])] + ... + [absolute value of ([F.sub.k-1])] [less than or equal to] 8n - 3 - (4n - 4) = 4n + 1.

Case 2.1 ([absolute value of ([F.sub.i])] [less than or equal to] 4n - 5 for i [member of] {1,2, ..., k - 1}). By Corollary 9, XQ[i] - [F.sub.i] is connected for i [member of] {1,2 ..., k - 1}. Since [k.sup.n-1] > 8n - 13, X[Q.sup.k.sub.n] [V(XQ[1] - [F.sub.1]) [union] ... [union] V(XQ[k - 1] - [F.sub.k-1])] is connected. By Corollary 9, XQ[0] - [F.sub.0] is connected or XQ[0] - [F.sub.0] has two components, one of which is an isolated vertex. Since [k.sup.n-1] - 1 > 8n - 13, X[Q.sup.k.sub.n] - F is connected (a contradiction) or X[Q.sup.k.sub.n] - F has two components, one of which is an isolated vertex.

Case 2.2 [mathematical expression not reproducible]. In this case, [absolute value of ([F.sup.n-1])] [less than or equal to] 5 and [absolute value of ([F.sub.i])] [less than or equal to] 5 for i [member of] {1, ..., k - 1} \ {[i.sub.0]}. Since [mathematical expression not reproducible]. By Corollary 9, XQ[i] - [F.sub.i] is connected for i [member of] {1, ..., k-1}\{[i.sub.0]}. Therefore, [mathematical expression not reproducible] is connected.

Case 2.2.1 (XQ[0] - [F.sub.0] is connected and [mathematical expression not reproducible] is connected). Since [k.sup.n-1] > 5, X[Q.sup.k.sub.n] is connected; a contradiction to that F is an edge cut of X[Q.sup.k.sub.n].

Case 2.2.2 (XQ[0] - [F.sub.0] is connected and [mathematical expression not reproducible] is disconnected). By the induction hypothesis, [mathematical expression not reproducible] has two components, one of which is an isolated vertex. Since [k.sup.n-1] - 1 > 4n - 5, X[Q.sup.k.sub.n] - F is connected (a contradiction) or X[Q.sup.k.sub.n] - F has two components, one of which is an isolated vertex.

Case 2.2.3 (XQ[0] - [F.sub.0] is disconnected and [mathematical expression not reproducible] is disconnected). By the induction hypothesis, XQ[0] - [F.sub.0] has two components, one of which is an isolated vertex u and [mathematical expression not reproducible] has two components, one of which is an isolated vertex v. Suppose that u is adjacent to v in X[Q.sup.k.sub.n] - F. Since [absolute value of ([F.sup.n-1])] [less than or equal to] 5, by Proposition 6, X[Q.sup.k.sub.n] is connected; a contradiction to that F is an edge cut ofX[Q.sup.k.sub.n]. Suppose that u is not adjacent to V in X[Q.sup.k.sub.n] - F. Since [absolute value of ([F.sup.n-1])] [less than or equal to] 5, XQ[0] - [F.sub.0] has two components, one of which is an isolated vertex or X[Q.sup.k.sub.n] is connected; a contradiction to that F is an edge cut of X[Q.sup.k.sub.n].

Case 3 (4n + 2 [less than or equal to] [absolute value of ([F.sub.0])] [less than or equal to] 8n - 11). In this case, [absolute value of ([F.sub.1])] + ... + [absolute value of ([F.sub.k-1])] [less than or equal to] 8n - 3- (4n + 2) = 4n - 5. Therefore, [absolute value of ([F.sub.i])] [less than or equal to] 4n - 5 for i [member of] {1, 2 ..., k-1}. By Corollary 9, XQ[i] - [F.sub.i] is connected for i [member of] {1, 2 ..., k-1}. Since [k.sup.n-1] > 4n - 5, X[Q.sup.k.sub.n] [V(XQ[1] - [F.sub.1])[union] ... [union] V(XQ[k - 1] - [F.sub.k-1])] is connected. By the induction hypothesis, XQ[0] - [F.sub.0] has two components, one of which is an isolated vertex. Since [k.sup.n-1] - 1 > 4n - 5, X[Q.sup.k.sub.n] - F is connected (a contradiction) or X[Q.sup.k.sub.n] - F has two components, one of which is an isolated vertex.

Case 4 (8n - 10 [less than or equal to] [absolute value of ([F.sub.0])] [less than or equal to] 8n - 3). In this case, [absolute value of ([F.sub.1])] + ... + [absolute value of ([F.sub.k-1])] [less than or equal to] 7 and [absolute value of ([F.sup.n-1])] [less than or equal to] 7. Similarly to Case 3, X[Q.sup.k.sub.n] [V(XQ[1] - [F.sub.1]) [union] ... [union] V(XQ[k - 1] - [F.sub.k-1])] is connected. Since [absolute value of ([F.sup.n-1])] [less than or equal to] 7, X[Q.sup.k.sub.n] - F is connected (a contradiction) or X[Q.sup.k.sub.n] - F has two components, one of which is an isolated vertex.

Theorem 16. Let X[Q.sup.k.sub.n] be the expanded k-ary n-cube with n [greater than or equal to] 3 and even k [greater than or equal to] 6. Then [lambda]' (X[Q.sup.k.sub.n]) = 8n - 2.

Proof. By Lemma 11, [lambda]' (X[Q.sup.k.sub.n]) [less than or equal to] 8n - 2. By Proposition 15, [lambda]'(X[Q.sup.k.sub.n]) [greater than or equal to] 8n - 2. Therefore, [lambda]'(X[Q.sup.k.sub.n]) = 8n - 2.

Theorem 17. Let X[Q.sup.k.sub.n] be the expanded k-ary n-cube with n [greater than or equal to] 3 and even k [greater than or equal to] 6. en X[Q.sup.k.sub.n] is super restricted edge-connected.

Proof. We can partition X[Q.sup.k.sub.n] into k disjoint subgraphs X[Q.sup.k.sub.n][0], X[Q.sup.k.sub.n][1], ..., X[Q.sup.k.sub.n][k - 1] (abbreviated as XQ[0], XQ[1], ..., XQ[k - 1], if there is no ambiguity), where every vertex [u.sub.0][u.sub.1] ...[u.sub.n-1] [member of] V(X[Q.sup.k.sub.n]) has a fixed integer i in the last position [u.sub.n-1] for i [member of] {0, 1, ..., k - 1}. By Proposition 3, each XQ[i] is isomorphic to X[Q.sup.k.sub.n-1] for 0 [less than or equal to] i [less than or equal to] k - 1. Let F be a minimum restricted edge cut of X[Q.sup.k.sub.n]. By Theorem 16, [absolute value of (F)] = 8n - 2. Let [F.sub.i] = F [intersection] E(XQ[i]) for i [member of] {0, 1, 2, ..., k - 1} with [absolute value of ([F.sub.0])] = max{[absolute value of ([F.sub.i])] : 0 [less than or equal to] i [less than or equal to] k - 1}. Let [F.sup.n-1] = F [intersection] (E(X[Q.sup.k.sub.n]) [[summation].sup.k-1.sub.i=0] E(X[Q.sup.k.sub.n][i])). We consider the following cases.

Case 1 ([absolute value of ([F.sub.0])] [less than or equal to] 4n - 5). Since [absolute value of ([F.sub.0])] = max{[absolute value of ([F.sub.i])] : 0 [less than or equal to] i [less than or equal to] k - 1}, [absolute value of ([F.sub.i])] [less than or equal to] 4n - 5 for i [member of] {1, 2, ..., k - 1}. By Corollary 9, XQ[i] - F is connected for i [member of] {0, 1, ..., k - 1}. Since 4[k.sup.n-1] > 8n - 2 (n [greater than or equal to] 2), X[Q.sup.k.sub.n] - F is connected; a contradiction to that F is an edge cut of X[Q.sup.k.sub.n].

Case 2 (4n - 4 [less than or equal to] [absolute value of ([F.sub.0])] [less than or equal to] 4n + 2). In this case, [absolute value of ([F.sub.1])] + ... + [absolute value of ([F.sub.k-1])] [less than or equal to] 8n - 2 - (4n - 4) = 4n + 2.

Case 2.1 ([absolute value of ([F.sub.i])] [less than or equal to] 4n - 5 for i [member of] {1, 2, ..., k - 1}). By Corollary 9, XQ[i] - [F.sub.i] is connected for i [member of] {1, 2 ..., k - 1}. Since 4[k.sup.n-1] > 8n - 2, X[Q.sup.k.sub.n][V(XQ[1] - [F.sub.1]) [union] ... [union] V(XQ[k - 1] - [F.sub.k-1])] is connected. By Proposition 15, XQ[0] - [F.sub.0] is connected or XQ[0] - [F.sub.0] has two components, one of which is an isolated vertex. Since 4([k.sup.n-1] - 1) > 8n - 2, X[Q.sup.k.sub.n] - F is connected or X[Q.sup.k.sub.n] - F has two components, one of which is an isolated vertex' a contradiction to that F is a restricted edge cut of X[Q.sup.k.sub.n].

Case 2.2 [mathematical expression not reproducible]. In this case, [absolute value of ([F.sup.n-1])] [less than or equal to] 6 and [absolute value of ([F.sub.i])] [less than or equal to] 6 for i [member of] {1, ..., k - 1} \ {[i.sub.0]}. By Corollary 9, XQ[i] - [F.sub.i] is connected for i [member of] {1, ..., k-1}\{[i.sub.0]}. Therefore, [mathematical expression not reproducible] is connected.

Case 2.2.1 (XQ[0] - [F.sub.0] is connected and [mathematical expression not reproducible] is connected). Since [k.sup.n-1] > 6, X[Q.sup.k.sub.n] is connected; a contradiction to that F is an edge cut of X[Q.sup.k.sub.n].

Case 2.2.2 (XQ[0] - [F.sub.0] is connected and [mathematical expression not reproducible] is disconnected). By Proposition 15, [mathematical expression not reproducible] has two components, one of which is an isolated vertex. Therefore, X[Q.sup.k.sub.n] - F is connected or X[Q.sup.k.sub.n] - F has two components, one of which is an isolated vertex; a contradiction to that F is a restricted edge cut of X[Q.sup.k.sub.n].

Case 2.2.3 (XQ[0] - [F.sub.0] is disconnected and [mathematical expression not reproducible] is disconnected). By Proposition 15, XQ[0] - [F.sub.0] has two components, one of which is an isolated vertex u and [mathematical expression not reproducible] has two components, one of which is an isolated vertex v. Suppose that u is adjacent to v in X[Q.sup.k.sub.n] - F. Since [absolute value of ([F.sup.n-1])] [less than or equal to] 6, by Proposition 6, X[Q.sup.k.sub.n] is connected (a contradiction) XQ[0]-[F.sub.0] has two components, one of which is an isolated vertex (a contradiction) or X[Q.sup.k.sub.n] - F has two components, one of which is a [K.sub.2]. Suppose that u is not adjacent to V in X[Q.sup.k.sub.n] - F. Since [absolute value of ([F.sup.n-1])] [less than or equal to] 6, XQ[0] - [F.sub.0] has two components, one of which is an isolated vertex or X[Q.sup.k.sub.n] is connected, a contradiction to that F is a restricted edge cut of X[Q.sup.k.sub.n].

Case 3 (4n + 3 [less than or equal to] [absolute value of ([F.sub.0])] [less than or equal to] 8n - 11). In this case, [absolute value of ([F.sub.1])] + ... + [absolute value of ([F.sub.k-1])] [less than or equal to] 8n - 2 - (4n + 3) = 4n - 5. Therefore, [absolute value of ([F.sub.i])] [less than or equal to] 4n - 5 for i [member of] {1, 2 ..., k - 1}. By Corollary 9, XQ[i] - [F.sub.i] is connected for i [member of] {1, 2 ..., k - 1}. Since [k.sup.n-1] > 4n - 5, X[Q.sup.k.sub.n] [V(XQ[1] - [F.sub.1]) [union] ... [union] V(XQ[k - 1] - [F.sub.k-1])] is connected. By Proposition 15, XQ[0] - [F.sub.0] has two components, one of which is an isolated vertex. Since [k.sup.n-1] - 1 > 4n - 5, X[Q.sup.k.sub.n] - F is connected or X[Q.sup.k.sub.n] - F has two components, one of which is an isolated vertex; a contradiction to that F is a restricted edge cut of X[Q.sup.k.sub.n].

Case 4 ([absolute value of ([F.sub.0])] = 8n - 10). In this case, [absolute value of ([F.sub.1])] + ... + [absolute value of ([F.sub.k-1])] [less than or equal to] 8 and [F.sub.n-1] [less than or equal to] 8.

X[Q.sup.k.sub.n] is connected (a contradiction), XQ[0] - [F.sub.0] has two components, one of which is an isolated vertex (a contradiction), or X[Q.sup.k.sub.n] - F has two components, one of which is a [K.sub.2].

Case 5 (8n - 9 [less than or equal to] [absolute value of ([F.sub.0])] [less than or equal to] 8n - 2). In this case, [absolute value of ([F.sub.1])] + ... + [absolute value of ([F.sub.k-1])] [less than or equal to] 7 and [absolute value of ([F.sub.n-1])] [less than or equal to] 7. Similarly to Case 3, X[Q.sup.k.sub.n] [V(XQ[1] - [F.sub.1]) [union] ... [union] V(XQ[k - 1] - [F.sub.k-1])] is connected. Since [absolute value of ([F.sub.n-1])] [less than or equal to]7, X[Q.sup.k.sub.n] - F is connected or X[Q.sup.k.sub.n] - F has two components, one of which is an isolated vertex; a contradiction to that F is a restricted edge cut of X[Q.sup.k.sub.n].

A super-[lambda] graph G to be m-super-[lambda] if G -S is still super-[lambda] for any edge subset S of G with [absolute value of (S)] [less than or equal to] m. The maximum integer of such m, written as [S.sub.[lambda]](G), is said to be the edge fault tolerance of G with respect to the super-[lambda] property.

Theorem 18 (see [17]). Let G be a regular graph. If G is super-[lambda]' and [delta](G) [greater than or equal to] 4, then [S.sub.[lambda]](G) = [delta](G) - 1.

By Theorems 17 and 18, we have the following theorem.

Theorem 19. Let X[Q.sup.k.sub.n] be the expanded k-ary n-cube with n [greater than or equal to] 3 and even k [greater than or equal to] 6. Then [S.sub.[lambda]](X[Q.sup.k.sub.n]) = 4n - 1.

Remarks on Theorem 19. Note that [S.sub.[lambda]](G) [less than or equal to] [delta](G) - 1. Since [delta](X[Q.sup.k.sub.n]) = 4n, [S.sub.[lambda]](X[Q.sup.k.sub.n]) is maximum.

A spanning subgraph of a graph G is a subgraph H with V(H) = V(G).

Proposition 20. The k-ary n-cube [Q.sup.k.sub.n] is a spanning subgraph of the expanded k-ary n-cube X[Q.sup.k.sub.n].

Proof. By the definitions of [Q.sup.k.sub.n] and X[Q.sup.k.sub.n], V([Q.sup.k.sub.n]) = V(X[Q.sup.k.sub.n]). Let uv [member of] E([Q.sup.k.sub.n]) with u = [u.sub.0][u.sub.1] ... [u.sub.n-1] and v = [v.sub.0][v.sub.1] ... [v.sub.n-1]. Then there exists an integer j [member of] {0, 1, ..., n - 1} such that [u.sub.j] = [v.sub.j] + g (mod k) and [u.sub.i] = [v.sub.i], for i [member of] {0, 1, ..., n-1}\{j} and g [member of] {1,-1} in [Q.sup.k.sub.n]. By the definition of X [Q.sup.k.sub.n], uv [member of] E(X[Q.sup.k.sub.n]).

A graph G is conditional faulty if each vertex of G is incident with at least two healthy edges.

Theorem 21 (see [18]). Let n [greater than or equal to] 2 and let k [greater than or equal to] 4 be even. Then the conditional faulty [Q.sup.k.sub.n] with at most 4n - 5 faulty edges is Hamiltonian.

By Theorem 21 and Proposition 20, we have the following corollary.

Corollary 22. The expanded k-ary n-cube is Hamiltonian.

3. Conclusions

In this paper, we investigate the problem of the super connectivity of the expanded k-ary n-cube X[Q.sup.k.sub.n]. It is proved that X[Q.sup.k.sub.n] is super edge-connected and super restricted edge-connected (n [greater than or equal to] 3). The work will help engineers to develop more different measures of the super connectivity based on application environment, network topology, network reliability, and statistics related to fault patterns.

https://doi.org/10.1155/2018/7867342

Data Availability

The data cited in the manuscript titled "the Edge Connectivity of Expanded k-Ary n-Cubes" are all published articles. There are no other data.

Conflicts of Interest

The authors declare that they have no conflicts of interest.

Acknowledgments

The authors would like to express their gratitude to the anonymous referees for their kind suggestions and corrections that helped improve the original manuscript. This work is supported by the National Natural Science Foundation of China (61772010) and the Science Foundation of Henan Normal University (Xiao 20180529, 20180454)

References

[1] J. A. Bondy and U. S. R. Murty, Graph eory with Applications, Macmillan Press, New York, NY, USA, 1976.

[2] P. Bonsma, N. Ueffing, and L. Volkmann, "Edge-cuts leaving components of order at least three," Discrete Mathematics, vol. 256, no. 1-2, pp. 431-439, 2002.

[3] J. Ou, "Edge cuts leaving components of order at least m," Discrete Mathematics, vol. 305, no. 1-3, pp. 365-371, 2005.

[4] Z. Zhang and J. Yuan, "A proof of an inequality concerning k- restricted edge connectivity," Discrete Mathematics, vol. 304, no. 1-3, pp. 128-134, 2005.

[5] S. Wang, G. Zhang, and K. Feng, "Edge fault tolerance of Cartesian product graphs on super restricted edge connectivity," e Computer Journal, vol. 61, no. 5, pp. 761-772, 2018.

[6] L. Shang and H. Zhang, "Super restricted edge-connectivity of graphs with diameter 2," Discrete Applied Mathematics: The Journal of Combinatorial Algorithms, Informatics and Computational Sciences, vol. 161, no. 3, pp. 445-451, 2013.

[7] S. Wang, M. Wang, and L. Zhang, "A sufficient condition for graphs to be super k-restricted edge connected," Discussiones Mathematicae Graph Theory, vol. 37, no. 3, pp. 537-545, 2017.

[8] B. Bose, B. Broeg, Y. Kwon, and Y. Ashir, "Lee distance and topological properties of k-ary n-cubes," Institute of Electrical and Electronics Engineers. Transactions on Computers, vol. 44, no. 8, pp. 1021-1030, 1995.

[9] K. Day and A. E. Al-Ayyoub, "Fault diameter of k-ary n-cube networks," IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 9, pp. 903-907, 1997.

[10] J. Yuan, A. Liu, X. Ma, X. Liu, X. Qin, andJ. Zhang, "The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC modeland MM* model," IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 4, pp. 1165-1177, 2015.

[11] R. Kessler and J. Schwarzmeier, "Cray T3D: a new dimension for cray research," in Proceedings of the 38th IEEE Computer Society International Conference, pp. 176-182, San Francisco, CA, USA, 1993.

[12] N. Michael and J. William, "Dally, system design of the J-machine," in Proceedings of the sixth MIT conference on Advanced research in VLSI, pp. 179-194, MIT Press, Cambridge, 1990.

[13] C. Peterson, J. Sutton, and P. Wiley, "iWarp: A 100-MOPS, LIW Microprocessor for Multicomputers," IEEE Micro, vol. 11, no. 3, pp. 26-29, 1991.

[14] N. R. Adiga, M. A. Blumrich, D. Chen et al., "Blue Gene/L torus interconnection network," IBM Journal of Research and Development, vol. 49, no. 2-3, pp. 265-276, 2005.

[15] Y. Xiang and I. A. Stewart, "Augmented k-ary n-cubes," Information Sciences, vol. 181, no. 1, pp. 239-256, 2011.

[16] M. Wang, Y. Lin, and S. Wang, "The connectivity and nature diagnosability of expanded k-ary n-cubes," RAIRO Theoretical Informatics and Applications, vol. 51, no. 2, pp. 71-89, 2017.

[17] Y. Hong, J. Meng, and Z. Zhang, "Edge fault tolerance of graphs with respect to super edge connectivity," Discrete Applied Mathematics: The Journal of Combinatorial Algorithms, Informatics and Computational Sciences, vol. 160, no. 4-5, pp. 579-587, 2012.

[18] Y. A. Ashir and I. A. Stewart, "Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes," SIAM Journal on Discrete Mathematics, vol. 15, no. 3, pp. 317-328, 2002.

Shiying Wang (iD) (1) and Mujiangshan Wang (2)

(1) School of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan 453007, China

(2) School of Electrical Engineering and Computer Science, The University of Newcastle NSW 2308, Australia

Correspondence should be addressed to ShiyingWang; wangshiying@htu.edu.cn

Received 9 June 2018; Accepted 19 September 2018; Published 2 October 2018

Academic Editor: Seenith Sivasundaram
COPYRIGHT 2018 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Wang, Shiying; Wang, Mujiangshan
Publication:Discrete Dynamics in Nature and Society
Date:Jan 1, 2018
Words:9859
Previous Article:Extended Oligopolies with Pollution Penalties and Rewards.
Next Article:Existence Results for Fractional Hahn Difference and Fractional Hahn Integral Boundary Value Problems.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters