# The Edge Connectivity of Expandedk-Ary n-Cubes

Authors: Shiying Wang; Mujiangshan Wang
Journal: Discrete Dynamics in Nature and Society
 (2018)

---

## Abstract

Mass data processing and complex problem solving have higher and higher demands for performance of multiprocessor systems. Many multiprocessor systems have interconnection networks as underlying topologies. The interconnection network determines the performance of a multiprocessor system. The network is usually represented by a graph where nodes (vertices) represent processors and links (edges) represent communication links between processors. For the networkG, two vertices u and v of G are said to be connected if there is a (u,v)-path in 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. For a connected network G=(V,E), its inverse problem is that G-F is disconnected, where F⊆V or F⊆E. The connectivity or edge connectivity is the minimum number of F. Connectivity plays an important role in measuring the fault tolerance of the network. As a topology structure of interconnection networks, the expanded k-ary n-cube XQnk has many good properties. In this paper, we prove that (1) XQnk is super edge-connected (n≥3); (2) the restricted edge connectivity of XQnk is 8n-2 (n≥3); (3) XQnk is super restricted edge-connected (n≥3).


---

## Body

## 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 graphG=(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 V1,V2,…,Vω such that two vertices u and v of G are connected if and only if both u and v belong to the same set Vi. The subgraphs G[V1],G[V2],…,G[Vω] 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⊆V or F⊆E. The connectivity or edge connectivity is the minimum number of F. Connectivity plays an important role in measuring the fault tolerance of the network.LetG=(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 dG(v) of a vertex v is the number of edges incident with v. We denote by δ(G) the minimum degrees of vertices of G. For any vertex v, we define the neighborhood NG(v) of v in G to be the set of vertices adjacent to v. If u∈NG(v), then u is called a neighbor or a neighbor vertex of v. Let S⊆V. We use NG(S) to denote the set ∪v∈SNGv∖S. A graph G is said to be k-regular if for any vertex v, dG(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 λk(G), is defined as the cardinality of a minimum k-restricted edge cut. For any positive integer k, let ξk(G)=min⁡X,X¯:X=k,GXis connected. For many graphs, it has been shown that ξk(G) is an upper bound on ξk(G) [2–4]. A λk-connected graph G is λk-optimal if λk(G)=ξk(G). The following is the definition on super-λk graphs used in our manuscript.Definition 1 (see [5]).
Aλk-connected graph G is super k-restricted edge-connected (or super-λ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 ofG is called the edge connectivity of G and is denoted by λ(G). The 2-restricted edge connectivity of G is called the restricted edge connectivity of G and is denoted by λ′(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-λk have been studied by several authors; see [6, 7].Thek-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 XQnk. The following is the definition.Definition 2 (see [16]).
The expandedk-ary n-cube, denoted by XQnk (n≥1 and even k≥6), is a graph consisting of kn vertices {u0u1…un-1:0≤ui≤k-1,0≤i≤n-1}. Two vertices u=u0u1…un-1 and v=v0v1…vn-1 are adjacent if and only if there exists an integer j∈{0,1,…,n-1} such that, for some g∈{1,-1,2,-2}, we have uj=vj+g (mod k) and ui=vi for all i∈0,1,…,n-1∖{j}.For clarity of presentation, we omit writing “(modk)” in similar expressions for the remainder of the paper. In this paper, we prove that (1) XQnk is super edge-connected (n≥3); (2) the restricted edge connectivity of XQnk is 8n-2 (n≥3); (3) XQnk is super restricted edge-connected (n≥3).


## 2. The Connectivity of Expandedk-Ary n-Cubes

We can partitionXQnk into k disjoint subgraphs XQnk[0],XQnk[1],…,XQnk[k-1] (abbreviated as XQ[0],XQ[1],…,XQ[k-1], if there is no ambiguity), where every vertex u=u0u1…un-1∈V(XQnk) has a fixed integer i in the last position un-1 for i∈{0,1,…,k-1}. Let u∈V(XQ[i]). Then Nu∖V(XQ[i]) is said to be outside neighbor vertices of u.Proposition 3 (see [16]).
EachXQ[i] is isomorphic to XQn-1k for 0≤i≤k-1.Proposition 4.
The expandedk-ary n-cube is the Cartesian product of n expanded k-ary 1-cubes, i.e., XQnk=XQ1k⊗XQ1k⊗…⊗XQ1k︸n.Proof.
We proveXQnk=XQ1k⊗XQ1k⊗…⊗XQ1k︸n by the induction on n. Now define a bijection from V(XQ2k) to V(XQ1k⊗XQ1k) given by (1)φ:u1u0→u1u0.Note VXQ2k=VXQ1k⊗XQ1k=k2. Let uv∈E(XQ2k) with u=u1u0 and v=v1v0. Then (1), if u1=v1, u0=v0+g (mod k) for g∈{1,-1,2,-2}; (2), if u0=v0, u1=v1+g (mod k) for g∈{1,-1,2,-2}. Suppose that u1=v1, u0=v0+g. Then u0v0∈E(XQ1k). By the definition of XQ1k⊗XQ1k, uv∈E(XQ1k⊗XQ1k)). Suppose that u0=v0, u1=v1+g. Similarly, uv∈E(XQ1k⊗XQ1k)).
Conversely, letuv∈E(XQ1k⊗XQ1k)) with u=(u1u0) and v=(v1v0). Then u1=v1, u0v0∈E(XQ1k) or u0=v0, u1v1∈E(XQ1k). Suppose that u1=v1 and u0v0∈E(XQ1k). By the definition of XQ1k, u0=v0+g (mod k) for g∈{1,-1,2,-2}. By the definition of XQ2k, uv∈E(Q2k). Suppose that u0=v0 and u1v1∈E(XQ1k). Similarly, uv∈E(Q2k). This implies that the result is true for n=2. Assume that the result holds for n=m-1, i.e., XQm-1k=XQ1k⊗XQ1k⊗…⊗XQ1k︸m-1 for m≥3. Then XQ1k⊗XQ1k⊗…⊗XQ1k︸m=(XQ1k⊗XQ1k⊗…⊗XQ1k︸m-1)⊗XQ1k=XQm-1k⊗XQ1k. We will prove that XQmk=XQ1k⊗XQm-1k. Now define a bijection from V(XQmk) to V(XQ1k⊗XQm-1k) given by (2)φ:um-1um-2⋯u0→um-1,um-2⋯u0.Note VXQmk=VXQ1k⊗XQm-1k=km. Let uv∈E(XQmk) with u=um-1um-2⋯u0, v=vm-1vm-2…v0, u′=um-2⋯u0, and v′vm-2…v0,
By Proposition3, each XQmk[i] is isomorphic to XQm-1k (i in the last position um-1). Suppose that uv∈E(XQmk[i]). Then um-1=vm-1=i. By the definition of XQ1k⊗XQm-1k, uv∈E(XQ1k⊗XQm-1k). Suppose that uv∈EXQmk∖∑i=0k-1EXQmki. Then, by the definition of XQmk[i], um-1=vm-1+g and ui=vi for i∈{0,1,…,m-2} and g∈{1,-1,2,-2}. Therefore, um-1vm-1∈E(XQ1k) and ui=vi for i∈{0,1,…,m-2}. By the definition of XQ1k⊗XQm-1k and uv∈E(XQ1k⊗XQm-1k).
Conversely, letuv∈E(XQ1k⊗XQm-1k)). Suppose that um-1=vm-1 and u′v′∈E(XQm-1k)). By the definition of XQm-1k, there exists an integer j∈{0,1,…,m-2} such that uj=vj+g (mod k) and ui=vi, for i∈0,1,…,m-2∖{j} and g∈{1,-1,2,-2}. Note that um-1=vm-1. By the definition of XQmk, uv∈E(XQmk). Suppose that um-1vm-1∈E(XQ1k) and u′=v′. By the definition of XQ1k, ui=vi+g. Note that u′=v′. By the definition of XQmk, uv∈E(XQmk).The automorphism group of a graphG is transitive if there exists an automorphism φ to any pair u,v of vertices in G such that φ(u)=v. In this case, G is called vertex transitive.Proposition 5 (see [16]).
X Q n k is 4n-regular, vertex transitive.Proposition 6 (see [16]).
Letu∈V(XQ[i]). Then four outside neighbor vertices of u are in four different XQj′s.Theorem 7 (see [16]).
LetXQnk be the expanded k-ary n-cube with n≥1 and even k≥6. Then the connectivity κ(XQnk)=4n.Theorem 8 (see [1]).
LetG be a connected graph. Then κ(G)≤λ(G)≤δ(G).By Proposition5 and Theorems 7 and 8, we have the following corollary.Corollary 9.
λ ( X Q n k ) = 4 n.Theorem 10.
LetXQnk be the expanded k-ary n-cube with n≥3 and even k≥6. Then XQnk is super edge-connected.Proof.
By Corollary9, λ(XQnk)=4n. Let F⊆E(XQnk) with F=4n be any minimum edge cut of XQnk. We can partition XQnk into k disjoint subgraphs XQ[0],XQ[1],…,XQ[k-1]. By Proposition 3, each XQ[i] is isomorphic to XQn-1k for 0≤i≤k-1. Let Fi=F∩E(XQ[i]) for i∈{0,1,2,…,k-1} with F0=max⁡Fi:0≤i≤k-1. Let Fn-1=F∩(EXQmk∖∑i=0k-1E(XQmk[i])). Then F=Fn-1∪F0∪⋯∪Fk-1. Since n≥3, kn-1>4n holds, we consider the following cases.
Case  1 (F0≤4n-5). Since F0=max⁡Fi:0≤i≤k-1, Fi≤4n-5. By Corollary 9, XQ[i]-Fi is connected. Since kn-1>4n and there is a complete matching between XQ[i] and XQ[i+1] for i∈{0,1,…,k-2}, XQnk-F is connected; a contradiction to that F is an edge cut of XQnk.
Case  2 (F0=4n-4). Since n≥3, 8n-8>4n holds hence there is only one F0 such that F0=4n-4. Therefore, Fi≤4n-5 for i∈{1,…,k-1}. By Corollary 9, XQ[i]-Fi is connected for i∈{1,…,k-1}. Since kn-1>4n and there is a complete matching between XQ[i] and XQ[i+1] for i∈{0,1,…,k-2}, XQnk[∪i=1k-1V(XQ[i]-Fi)] is connected.
Case  2.1 (XQ[0]-F0 is connected). Since there is a complete matching between XQ[i] and XQ[i+1] for i∈{0,1,…,k-2}, XQnk-F is connected; a contradiction to that F is an edge cut of XQnk.
Case  2.2 (XQ[0]-F0 is not connected). Since F0=4n-4 and F=4n, Fn-1≤4 holds. Let Fn-1≤3. By Proposition 6, XQnk-F is connected; a contradiction to that F is an edge cut of XQnk. Let Fn-1=4. Let B1,…,Bj(j≥2) be the components of XQ[0]-F0. Suppose VBi≥2 for i=1,…,j. By Proposition 6, |VBi∩∪i=1k-1VXQi≥8. Since Fn-1=4, XQnk-F is connected, a contradiction to that F is an edge cut of XQnk. Therefore, there is a Bi such that Bi=1. Let V(Bi)={b}. Since dXQ0(b)=4n-4=F0, there is only a Bi such that Bi=1. If b is incident with each of F0, then XQnk-F has two components, one of which is an isolated vertex. If b is not incident with each of F0, then XQnk-F is connected; a contradiction to that F is an edge cut of XQnk.
Case  3 (4n-3≤F0≤4n). In this case, Fn-1≤3 and XQnk[∪i=1k-1V(XQ[i]-Fi)] is connected. By Proposition 6, XQnk-F is connected, a contradiction to that F is a edge cut of XQnk.
By Cases 1–3,XQnk is super edge-connected.Lemma 11.
LetXQnk be the expanded k-ary n-cube with n≥3 and even k≥6. Then λ′(XQnk)≤8n-2.Proof.
Letu=00…0︸n and v=00…0︸n-11. Then u is adjacent to v and u,v∈V(XQ[0]). Let E′=u,v,u,v¯. Then E′=8n-2 and E′∩E(XQ[i])=∅ for i∈{1,…,k-1}. Therefore, XQnk[∪i=1k-1V(XQ[i]-E′)] is connected. Let x∈VXQ0∖{u,v}. Then [{x},x¯]∩E′=∅. Therefore, XQnk[{x}∪(∪i=1k-1V(XQ[i]-E′))] is connected and hence XQnk-F has two components G1(VG1=2) and G2(VG1≥2). By the definition of λ′, λ′(XQnk)≤8n-2.Proposition 12.
LetXQ1k be the expanded k-ary 1-cube with even k≥6, and let F⊆E(XQ1k) with F≤5. If XQ1k-F is disconnected, then XQ1k-F has two components, one of which is an isolated vertex.Proof.
IfF≤3, by Corollary 9, then XQ2k-F is connected, a contradiction. Let F=4. By Proposition 5, XQ1k is 4-regular. Therefore, there is one F such that XQ1k-F has two components, one of which is an isolated vertex. Let F=5. Suppose that XQ1k-F has two or more components which have order at least 2. Choose a component A of XQ1k-F with VA≥2 so that VA is as small as possible. Then 2≤VA≤k/2. In view of Proposition 5, we may assume that V(A)=∪1≤i≤p{mi,mi+1,…,mi+hi-1} and 1,…,k-1∖VA=∪1≤i≤p{mi+hi,mi+hi+1,…,mi+1-1}, where p≥1 and 0=m1<m1+h1<m2<m2+h2<…<mp<mp+hp<mp+1=k. Then VA=h1+h2+⋯+hp and 0,1,…,k-1∖VA=(m2-(m1+h1))+(m3-(m2+h2))+⋯+(k-(mp+hp)). If p≥3, then the edge set {{m1+h1-1,m1+h1},{m2-1,m2},{m2+h2-1,m2+h2},{m3-1,m3},{m3+h3-1,m3+h3},{m4-1,m4}}⊆F (in the case where p=3, we take {m4-1,m4}={k-1,0}), and hence F≥6, a contradiction to that F=5. Thus 1≤p≤2. Suppose that p=2. Since 1,…,k-1∖VA≥3, we have m2-h1≥2 or k-(m2+h2)≥2. We may assume m2-h1≥2. Then h1+1,m2-2∈{1,…,k-1}∖V(A), which implies {{h1-1,h1},{h1-1,h1+1},{m2-2,m2},{m2-1,m2},{m2+h2-1,m2+h2},{k-1,0}}⊆F, and hence F≥6, a contradiction to that F=5. Thus p=1. Since 1,…,k-1∖VA≥VA≥2, it follows that h1≥2 and k-h1≥2. Consequently 1,h1-2∈V(A) and h1+1,k-2∈{1,…,k-1}∖V(A), which implies h1-2,h1,h1-1,h1,h1-1,h1+1,k-2,0,k-1,0,k-1,1⊆F. Therefore F≥6, a contradiction to that F=5 and hence XQ1k-F has two components, one of which is an isolated vertex.Proposition 13.
LetXQ1k be the expanded k-ary 1-cube with even k≥6, and let F⊆E(XQ1k) be a minimum 2-restricted edge cut of XQ1k. Then F=6.Proof.
By Proposition12, F≥6. Let 0,1,0,1¯. Then 0,1,0,1¯ is a 2-restricted edge cut of XQ1k and 0,1,0,1¯=6. Therefore, F=6.Proposition 14.
LetXQ2k be the expanded k-ary 2-cube with even k≥6, and let F⊆E(XQ2k) with F≤13. If XQ2k-F is disconnected, then XQ2k-F has two components, one of which is an isolated vertex.Proof.
We can partitionXQ2k into k disjoint subgraphs XQ2k[0],XQ2k[1],…,XQ2k[k-1] (abbreviated as XQ[0],XQ[1],…,XQ[k-1], if there is no ambiguity), where every vertex u0u1∈V(XQ2k) has a fixed integer i in the last position u1 for i∈{0,1,…,k-1}. By Proposition 3, each XQ[i] is isomorphic to XQn-1k for 0≤i≤k-1. By Corollary 9, λ(XQ[i])=4. Let Fi=F∩V(XQ[i]) for i∈0,1,2,…,k-1 with F0=max⁡Fi:0≤i≤k-1. Let Fn-1=F∩EXQ2k∖∑i=0k-1EXQ2ki. Then F=Fn-1∪F0∪⋯∪Fk-1. We consider the following cases.
Case  1 (F0≤3). Since F0=max⁡Fi:0≤i≤k-1, Fi≤3. By Corollary 9, XQi-F is connected. By Proposition 6 and 13<24, XQ2k-F is connected, a contradiction to that F is a cut of XQ2k.
Case  2 (F0=4). Since F0=max⁡Fi:0≤i≤k-1, Fi≤4. Since F1+⋯+F5≤9, there are at most three Fi’s such that Fi=4 for i∈1,2…,k-1.
Case  2.1 (F0=4 and Fi≤3 for i∈1,2…,k-1). By Corollary 9, XQ[i]-Fi is connected for i∈{1,2…,k-1}. By Proposition 6 and 13<24, XQ2k[V(XQ[1]-F1)∪⋯∪V(XQ[k-1]-Fk-1)] is connected. By Theorem 10, XQ[0]-F0 is connected or XQ[0]-F0 has two components, one of which is an isolated vertex. Since 13<20, XQ2k-F is connected (a contradiction) or XQ2k-F has two components, one of which is an isolated vertex.
Case  2.2 (F0=4, Fi0=4 and Fi≤3 for i∈1,2…,k-1∖i0). In this case, Fn-1≤5. Similarly to Case 2.1, XQ2k-F is connected (a contradiction) or XQ2k-F has two components, one of which is an isolated vertex.
Case  2.3 (F0=4, Fi0=4, Fj0=4 and Fi≤1 for i∈1,2…,k-1∖i0,j0). In this case, Fn-1≤1. Similarly to Case 2.1, XQ2k-F is connected, a contradiction.
Case  3 (F0=5). Since F0=max⁡Fi:0≤i≤k-1, Fi≤5. Since F1+⋯+F5≤8, there are at most two Fi’s such that Fi=4 for i∈1,2…,k-1.
Case  3.1 (F0=5 and Fi≤3 for i∈{1,2…,k-1}). By Corollary 9, XQ[i]-Fi is connected for i∈{1,2…,k-1}. By Proposition 6 and 13<24, XQ2k[V(XQ[1]-F1)∪⋯∪V(XQ[k-1]-Fk-1)] is connected. By Proposition 12, XQ[0]-F0 is connected or XQ2k-F has two components, one of which is an isolated vertex. Since 13<20, XQ2k-F is connected (a contradiction) or XQ2k-F has two components, one of which is an isolated vertex.
Case  3.2 (F0=5, Fi0=4 and Fi≤3 for i∈1,2…,k-1∖i0). In this case, Fn-1≤4. Similarly to Case 3.1, XQ2k-F is connected (a contradiction) or XQ2k-F has two components, one of which is an isolated vertex.
Case  3.3 (F0=5, Fi0=5 and Fi≤3 for i∈1,2…,k-1∖i0). In this case, Fn-1≤3. By Proposition 12, XQ[0]-F0 is connected or XQ2k-F has two components, one of which is an isolated vertex. Therefore, XQ2k-F is connected, a contradiction.
Case  4 (6≤F0≤13). In this case, Fn-1≤7 and F1+⋯+Fk-1≤7. Therefore, XQ[0]-F0 is connected (a contradiction) or XQ2k-F has two components, one of which is an isolated vertex.Proposition 15.
LetXQnk be the expanded k-ary n-cube with even k≥6, and let F⊆E(XQnk) with F≤8n-3. If XQnk-F is disconnected, then XQnk-F has two components, one of which is an isolated vertex.Proof.
We can partitionXQnk into k disjoint subgraphs XQnk[0],XQnk[1],…,XQnk[k-1] (abbreviated as XQ[0],XQ[1],…,XQ[k-1], if there is no ambiguity), where every vertex u0u1…un-1∈V(XQnk) has a fixed integer i in the last position un-1 for i∈{0,1,…,k-1}. By Proposition 3, each XQ[i] is isomorphic to XQn-1k for 0≤i≤k-1. Let F⊆E(XQnk) with F≤8n-3 and let XQnk-F is disconnected. Let Fi=F∩E(XQ[i]) for i∈{0,1,2,…,k-1} with F0=max⁡Fi:0≤i≤k-1. Let Fn-1=F∩EXQnk∖∑i=0k-1EXQnki. When n=2, the result holds by Proposition 14. We proceed by induction on n. Our induction hypothesis is that XQn-1k-F has two components, one of which is an isolated vertex for F≤8n-11 and n≥3. By Proposition 3, each XQ[i] is isomorphic to XQn-1k for 0≤i≤k-1. We consider the following cases.
Case  1 (F0≤4n-5). Since F0=max⁡Fi:0≤i≤k-1, Fi≤4n-5 for i∈{1,2,…,k-1}. By Corollary 9, XQ[i]-F is connected for i∈{0,1,…,k-1}. Since kn-1>8n-13 and there is a complete matching between XQ[i] and XQ[i+1], for i∈{0,1,…,k-2}, XQnk-F is connected; a contradiction to that F is a cut of XQnk.
Case  2 (4n-4≤F0≤4n+1). In this case, F1+⋯+Fk-1≤8n-3-(4n-4)=4n+1.
Case  2.1 (Fi≤4n-5 for i∈{1,2,…,k-1}). By Corollary 9, XQ[i]-Fi is connected for i∈{1,2…,k-1}. Since kn-1>8n-13, XQnk[V(XQ[1]-F1)∪⋯∪V(XQ[k-1]-Fk-1)] is connected. By Corollary 9, XQ[0]-F0 is connected or XQ[0]-F0 has two components, one of which is an isolated vertex. Since kn-1-1>8n-13, XQnk-F is connected (a contradiction) or XQnk-F has two components, one of which is an isolated vertex.
Case  2.2 (4n-4≤Fi0≤4n+1 for 1≤i0≤k-1). In this case, Fn-1≤5 and Fi≤5 for i∈{1,…,k-1}∖{i0}. Since F0=max⁡Fi:0≤i≤k-1, 4n-4≤Fi0≤4n-2. By Corollary 9, XQ[i]-Fi is connected for i∈{1,…,k-1}∖{i0}. Therefore, XQnk[∪i=1i0-1V(XQ[i]-Fi)∪∪i=i0+1k-1V(XQ[i]-Fi)] is connected.
Case  2.2.1 (XQ[0]-F0 is connected and XQ[i0]-Fi0 is connected). Since kn-1>5, XQnk is connected; a contradiction to that F is an edge cut of XQnk.
Case  2.2.2 (XQ[0]-F0 is connected and XQ[i0]-Fi0 is disconnected). By the induction hypothesis, XQ[i0]-Fi0 has two components, one of which is an isolated vertex. Since kn-1-1>4n-5, XQnk-F is connected ( a contradiction) or XQnk-F has two components, one of which is an isolated vertex.
Case  2.2.3 (XQ[0]-F0 is disconnected and XQ[i0]-Fi0 is disconnected). By the induction hypothesis, XQ[0]-F0 has two components, one of which is an isolated vertex u and XQ[i0]-Fi0 has two components, one of which is an isolated vertex v. Suppose that u is adjacent to v in XQnk-F. Since Fn-1≤5, by Proposition 6, XQnk is connected; a contradiction to that F is an edge cut of XQnk. Suppose that u is not adjacent to v in XQnk-F. Since Fn-1≤5, XQ[0]-F0 has two components, one of which is an isolated vertex or XQnk is connected; a contradiction to that F is an edge cut of XQnk.
Case  3 (4n+2≤F0≤8n-11). In this case, F1+⋯+Fk-1≤8n-3-(4n+2)=4n-5. Therefore, Fi≤4n-5 for i∈{1,2…,k-1}. By Corollary 9, XQ[i]-Fi is connected for i∈{1,2…,k-1}. Since kn-1>4n-5, XQnk[V(XQ[1]-F1)∪⋯∪V(XQ[k-1]-Fk-1)] is connected. By the induction hypothesis, XQ[0]-F0 has two components, one of which is an isolated vertex. Since kn-1-1>4n-5, XQnk-F is connected (a contradiction) or XQnk-F has two components, one of which is an isolated vertex.
Case  4 (8n-10≤F0≤8n-3). In this case, F1+⋯+Fk-1≤7 and Fn-1≤7. Similarly to Case 3, XQnk[V(XQ[1]-F1)∪⋯∪V(XQ[k-1]-Fk-1)] is connected. Since Fn-1≤7, XQnk-F is connected ( a contradiction) or XQnk-F has two components, one of which is an isolated vertex.Theorem 16.
LetXQnk be the expanded k-ary n-cube with n≥3 and even k≥6. Then λ′(XQnk)=8n-2.Proof.
By Lemma11, λ′(XQnk)≤8n-2. By Proposition 15, λ′(XQnk)≥8n-2. Therefore, λ′(XQnk)=8n-2.Theorem 17.
LetXQnk be the expanded k-ary n-cube with n≥3 and even k≥6. Then XQnk is super restricted edge-connected.Proof.
We can partitionXQnk into k disjoint subgraphs XQnk[0],XQnk[1],…,XQnk[k-1] (abbreviated as XQ[0],XQ[1], …, XQ[k-1], if there is no ambiguity), where every vertex u0u1…un-1∈V(XQnk) has a fixed integer i in the last position un-1 for i∈{0,1,…,k-1}. By Proposition 3, each XQ[i] is isomorphic to XQn-1k for 0≤i≤k-1. Let F be a minimum restricted edge cut of XQnk. By Theorem 16, F=8n-2. Let Fi=F∩E(XQ[i]) for i∈{0,1,2,…,k-1} with F0=max⁡Fi:0≤i≤k-1. Let Fn-1=F∩EXQnk∖∑i=0k-1EXQnki. We consider the following cases.
Case  1 (F0≤4n-5). Since F0=max⁡Fi:0≤i≤k-1, Fi≤4n-5 for i∈{1,2,…,k-1}. By Corollary 9, XQ[i]-F is connected for i∈{0,1,…,k-1}. Since 4kn-1>8n-2 (n≥2), XQnk-F is connected; a contradiction to that F is an edge cut of XQnk.
Case  2 (4n-4≤F0≤4n+2). In this case, F1+⋯+Fk-1≤8n-2-(4n-4)=4n+2.
Case  2.1 (Fi≤4n-5 for i∈{1,2,…,k-1}). By Corollary 9, XQ[i]-Fi is connected for i∈{1,2…,k-1}. Since 4kn-1>8n-2, XQnk[V(XQ[1]-F1)∪⋯∪V(XQ[k-1]-Fk-1)] is connected. By Proposition 15, XQ[0]-F0 is connected or XQ[0]-F0 has two components, one of which is an isolated vertex. Since 4(kn-1-1)>8n-2, XQnk-F is connected or XQnk-F has two components, one of which is an isolated vertex’ a contradiction to that F is a restricted edge cut of XQnk.
Case  2.2 (4n-4≤Fi0≤4n+2 for 1≤i0≤k-1). In this case, Fn-1≤6 and Fi≤6 for i∈{1,…,k-1}∖{i0}. By Corollary 9, XQ[i]-Fi is connected for i∈{1,…,k-1}∖{i0}. Therefore, XQnk[∪i=1i0-1V(XQ[i]-Fi)∪∪i=i0+1k-1V(XQ[i]-Fi)] is connected.
Case  2.2.1 (XQ[0]-F0 is connected and XQ[i0]-Fi0 is connected). Since kn-1>6, XQnk is connected; a contradiction to that F is an edge cut of XQnk.
Case  2.2.2 (XQ[0]-F0 is connected and XQ[i0]-Fi0 is disconnected). By Proposition 15, XQ[i0]-Fi0 has two components, one of which is an isolated vertex. Therefore, XQnk-F is connected or XQnk-F has two components, one of which is an isolated vertex; a contradiction to that F is a restricted edge cut of XQnk.
Case  2.2.3 (XQ[0]-F0 is disconnected and XQ[i0]-Fi0 is disconnected). By Proposition 15, XQ[0]-F0 has two components, one of which is an isolated vertex u and XQ[i0]-Fi0 has two components, one of which is an isolated vertex v. Suppose that u is adjacent to v in XQnk-F. Since Fn-1≤6, by Proposition 6, XQnk is connected ( a contradiction) XQ[0]-F0 has two components, one of which is an isolated vertex ( a contradiction) or XQnk-F has two components, one of which is a K2. Suppose that u is not adjacent to v in XQnk-F. Since Fn-1≤6, XQ[0]-F0 has two components, one of which is an isolated vertex or XQnk is connected, a contradiction to that F is a restricted edge cut of XQnk.
Case  3 (4n+3≤F0≤8n-11). In this case, F1+⋯+Fk-1≤8n-2-(4n+3)=4n-5. Therefore, Fi≤4n-5 for i∈{1,2…,k-1}. By Corollary 9, XQ[i]-Fi is connected for i∈{1,2…,k-1}. Since kn-1>4n-5, XQnk[V(XQ[1]-F1)∪⋯∪V(XQ[k-1]-Fk-1)] is connected. By Proposition 15, XQ[0]-F0 has two components, one of which is an isolated vertex. Since kn-1-1>4n-5, XQnk-F is connected or XQnk-F has two components, one of which is an isolated vertex; a contradiction to that F is a restricted edge cut of XQnk.
Case  4 (F0=8n-10). In this case, F1+⋯+Fk-1≤8 and Fn-1≤8.
X Q n k is connected ( a contradiction), XQ[0]-F0 has two components, one of which is an isolated vertex ( a contradiction), or XQnk-F has two components, one of which is a K2.
Case  5 (8n-9≤F0≤8n-2). In this case, F1+⋯+Fk-1≤7 and Fn-1≤7. Similarly to Case 3, XQnk[V(XQ[1]-F1)∪⋯∪V(XQ[k-1]-Fk-1)] is connected. Since Fn-1≤7, XQnk-F is connected or XQnk-F has two components, one of which is an isolated vertex; a contradiction to that F is a restricted edge cut of XQnk.A super-λ graph G to be m-super-λ if G-S is still super-λ for any edge subset S of G with S≤m. The maximum integer of such m, written as Sλ(G), is said to be the edge fault tolerance of G with respect to the super-λ property.Theorem 18 (see [17]).
LetG be a regular graph. If G is super-λ′ and δ(G)≥4, then Sλ(G)=δ(G)-1.By Theorems17 and 18, we have the following theorem.Theorem 19.
LetXQnk be the expanded k-ary n-cube with n≥3 and even k≥6. Then Sλ(XQnk)=4n-1.Remarks on Theorem19. Note that Sλ(G)≤δ(G)-1. Since δ(XQnk)=4n, Sλ(XQnk) is maximum.A spanning subgraph of a graphG is a subgraph H with V(H)=V(G).Proposition 20.
Thek-ary n-cube Qnk is a spanning subgraph of the expanded k-ary n-cube XQnk.Proof.
By the definitions ofQnk and XQnk, V(Qnk)=V(XQnk). Let uv∈E(Qnk) with u=u0u1…un-1 and v=v0v1…vn-1. Then there exists an integer j∈{0,1,…,n-1} such that uj=vj+g (mod k) and ui=vi, for i∈{0,1,…,n-1}∖{j} and g∈{1,-1} in Qnk. By the definition of XQnk, uv∈E(XQnk).A graphG is conditional faulty if each vertex of G is incident with at least two healthy edges.Theorem 21 (see [18]).
Letn≥2 and let k≥4 be even. Then the conditional faulty Qnk with at most 4n-5 faulty edges is Hamiltonian.By Theorem21 and Proposition 20, we have the following corollary.Corollary 22.
The expandedk-ary n-cube is Hamiltonian.


## 3. Conclusions

In this paper, we investigate the problem of the super connectivity of the expandedk-ary n-cube XQnk. It is proved that XQnk is super edge-connected and super restricted edge-connected (n≥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.



---

*Source: 7867342-2018-10-02.xml*