IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 51 (2013), 1189 ISSN 2232-2094 AVERAGE DISTANCE, SURFACE AREA, AND OTHER STRUCTURAL PROPERTIES OF EXCHANGED HYPERCUBES Sandi Klavzar Meijie Ma Ljubljana, August 23, 2013 Average distance, surface area. and other structural properties of exchanged hypercubes 00 CSF CSF Sandi Klavzar Faculty of Mathematics and Physics University of Ljubljana, Slovenia and Faculty of Natural Sciences and Mathematics University of Maribor, Slovenia and Institute of Mathematics, Physics and Mechanics, Ljubljana sandi.klavzar@fmf.uni-lj.si Meijie Ma Department of Mathematics Zhejiang Normal University Jinhua, Zhejiang, 321004, China mameij@mail.ustc.edu.cn Abstract Exchanged hypercubes [Loh et al., IEEE Transactions on Parallel and Distributed Systems 16 (2005) 866-874] are spanning subgraphs of hypercubes with about one half of their edges but still with many desirable properties of hypercubes. In this paper it is shown that also distance properties of exchanged hypercubes are comparable to the corresponding properties of hypercubes. The average distance and the surface area of exchanged hypercubes are computed and it is shown that exchanged hypercubes have asymptotically the same average distance as hypercubes. Several additional metric and other properties are also deduced and it is proved that exchanged hypercubes are prime with respect to the Cartesian product of graphs. Key words: interconnection network; exchanged hypercube; Wiener index; average distance; surface area; Cartesian product of graphs AMS Subj. Class.: 05C12, 05C82, 68M10 CD 1 Introduction Hypercubes form one of the fundamental models for interconnection networks. They are C! universal in the sense that the binary strings are naturally encoded into their topology. Jh ^ 1 CD 1 Jh Consequently, they possess numerous fine network properties such as small diameter, small density, and high connectivity At the same time, straightforward local routing is possible. Nevertheless, from several reasons different variations of hypercubes were proposed, let us mention here only Mobious cubes [5], folded hyper-star networks [16], Fibonacci cubes [17], folded cubes [19], k-ary n--cubes [28], and twisted-cubes [29]. An additional variation of hypercubes—exchanged hypercubes—is of our prime interest here. The exchanged hypercubes EH(s,t), proposed by Loh et al. [23], are graphs obtained by systematically removing edges from hypercubes. The number of vertices in EH(s,t) is equal to that of the (s + t + l)-dimensional hypercube, but the ratio of the number of edges in EH(s,t) to that of the (s +1 + l)-dimensional hypercube is 1/2 + l/(2(s + t + 1)) [4], Different properties of exchanged hypercubes were investigated by now. The bipancyclicity of them was investigated in [24], To measure the fault-tolerance of them, the connectivity and the super connectivity were determined in [20, 25, 26]. These results, in addition to those obtained in the seminal paper [23], indicate that the exchanged hypercubes keep numerous desirable properties of the hypercubes. In this paper we take a closer look to metric properties of exchanged hypercubes and some other related properties. Graphs considered here are simple, finite, and connected. The distance cI,g(u,v) between vertices u and v of a (connected) graph G is the usual shortest-path distance. If G will be clear from the context, we will simply write d(u,v). The Wiener index W(G) of a graph G is the sum of the distances between all unordered pairs of vertices of G. For instance, W(Kn) = Q), that is, the number of its edges. This graph invariant is one of the fundamental properties of (interconnection) networks, cf. [2, 4, 6, 18, 27]. On the other hand, the Wiener index of a graph is a central and one of the most studied invariants in mathematical chemistry, see for instance surveys [8, 9]. A concept closely related to the Wiener index is the surface area. If v is a vertex of a graph G and r a positive integer, then the r-surface area Bg,v(t) of G centered at v is the number of vertices at distance r from the fixed base vertex v. That is, the surface area is the size of the r-sphere around v. If G is vertex-transitive, then the surface area is independent of a selected vertex. The surface area of a network is interesting because many network properties and algorithms are directly related to it. Consequently, it has been studied for a variety of networks, cf. [6, 7, 14], The paper is organized as follows. In the next section we introduce the exchanged hypercubes in two equivalent ways and recall or deduce some of their basic properties. Then, in Section 3, we first determine the Wiener index of exchanged hypercubes. As a consequence it is demonstrated that asymptotically exchanged hypercubes and hypercubes have the same average distance. Then we determine the surface area and indicate that this result yields an alternative way to determine the Wiener index. In Section 4 we first consider several other distance-based invariants and then prove that the exchanged hypercubes are prime with respect to the Cartesian product operation. In the final section we point out that dual-cubes are particular instances of exchanged hypercubes and list some of consequences of our results for the dual-cubes. 2 Exchanged hypercubes: two definitions and some properties In this section we first introduce exchanged hypercubes and list some of their properties. Then we equivalently describe these cubes as the graphs obtained by adding a perfect matching between two collections of hypercubes and show how this point of view can be used to infer additional properties. Exchanged hypercubes are spanning subgraphs of hypercubes. Recall that if d is a positive integer, then the d-dimensional hypercube (or d-cube, for short) Qd, is the graph with vertex set {0, two vertices (strings) being adjacent if they differ in exactly one coordinate. The Hamming distance H(b, c) between binary strings b and c of the same length is the number of positions in which b and c differ. It is well known that d,Qd(u,v) = H(u,v) holds for any two vertices (alias strings) of Qd,. Let u = Ud-i...uo € {0,1 }d be a binary string, d > 1. If j > i, then we will use the notation u,j:i for the substring of u between Uj and Ui, that is, u,j:i = Uj .. .ih. For any integers s > 1 and t > 1, the exchanged hypercube EH(s,t) is the graph with the vertex set {0, l}i+i+1. Hence, if u € V(EH(s,t)), then its coordinates are us+t ■ ■ ■ ut+iUt ■ ■ ■ uiuo- Vertices u and v are adjacent if one of the following conditions is satisfied: (i) Us+t: 1 = Vs+t:l,Uo / V0, (ii) u0 = v0 = l,H(ut:i,vt:i) = 1, and us+p.t+1 = vs+t.t+1, (iii) u0 = v0 = 0, H(us+t:t+i,vs+t:t+i) = 1, and Up. 1 = Vpi. For instance, EH( 1,2) and EH(2,2) are shown in Fig. 1. , /1001 1101 \ v o ' \ w / \ cCiooo noob 11011 11111 4 /'- / \ / s ' JQ- -K / / X C^ S 0001 0101 / p ooio v "b-d / ono r""""""^oiooo onooh^^f 00000 00100^1 0011 0111 eh{ 1,2) 10011 10111 £#(2,2) Figure 1: Exchanged hypercubes EH{ 1,2) and EH{2,2) Clearly, EH(s,t) has 2i+i+1 vertices. Note also that if u € V{EH(s,t)) and u,0 = 0, then the degree of u is s +1, otherwise the degree of u is t +1. It is also straightforward that for any s and t, the exchanged hypercube EH(s,t) is isomorphic to EH(t,s). For practical purposes, another description of the exchanged hypercubes is useful. Note that the edge set of EH(s,t) is the disjoint union of sets Ei, E2, E3, where El = {uv : us+t: 1 = Vs+t:l,Uo / V0}, E-2 = {uv : Us+t:t+1 = Vs+t:t+l,H(ut:l,Vt:l) = 1 ,U0 = V0 = 1}, E3 = {uv : Up. 1 = Vpi,H(us+pt+i,vs+pt+i) = 1 ,u0 = v0 = 0}. In Fig. 1 the edges from Ei, E2 and E3 are represented by dashed lines, thin lines, and thick lines, respectively. Let EHi(s, t) be the subgraph of EH(s, t) induced by the edges E2. Then EHi(s, t) is the disjoint union of 2s copies of Qt- Indeed, fixing the leftmost s bits and fixing the rightmost bit to 1, the induced subgraph is isomorphic to Qt. Moreover, there are no edges between two such induced subgraphs isomorphic to Qt. Similarly, the subgraph EHo(s,t) of EH(s,t) induced by the edges E3 consists of 2* subgraphs isomorphic to Qs. Finally, the edges from E\ form a perfect matching of EH(s,t), it is a matching between EHq(s, t) and EHi(s, t). More precisely, let Q be an arbitrary copy of Qt from EHi(s,t). Then each vertex of Q has exactly one neigbor in EHo(s,t), each of these neighbors belongs to a different copy of Qs from EHo(s,t). For instance, in the graph EH(2,2) in Fig. 1, the subgraph EHi(2,2) consists of 4 copies of Q2 drawn with thin lines, the subgraph EHq(2,2) consists of 4 copies of Q2 drawn with thick lines, while the matching edges (that is, the edges from E\) are drawn with dashed lines. Using the above representation of the exchanged hypercubes it is immediate that \E(EH(s,t))\ = 2t(s'2s~1) + 2s(t2t~1) + 2t2s = 2i+i"1(s + t + 2), cf. [4], Since Qs+t+i has (s + t + l)2i+i edges, it thus follows that EH(s, t) has about, one half of the edges of the hypercube of the same dimension. As another property we have: Proposition 2.1 If s,t > 1, then the number of A-cycles of EH(s,t) is Proof. From the above representation we infer that a 4-cycle of EH(s, t) contains no edge between EHo(s,t) and EHi(s,t). It follows that any 4-cycle lies either in EHq(s, t) or in EHi(s, t). As these two subgraphs are disjoint unions of hypercubes Qs and Qt, respectively, and since Qn contains exactly 2n~'2{'") 4-cycles, cf. [15, Exercise 2.4], the assertion follows immediately. □ We have noted that the edges from E\ form a perfect matching of EH(s,t). But exchanged hypercubes contain many additional perfect matchings. Indeed, hypercubes contain a huge number of perfect matchings, cf. [11], hence any combination of separate perfect matchings in copies of Qs and Qt gives a perfect matching in EH(s,t). Moreover, Fink [10] proved that every perfect matching of Qd, d > 2, is contained in a Hamiltonian cycle. This result together with the second description of the exchanged hypercubes can be used to construct many Hamiltonian cycles in exchanged hypercubes EH(s, s), see [3]. The domination number 7(G) of a graph G is the order of a smallest set X C V(G) such that any vertex u e V(G) \ X has at least one neighbor in X. The exact value °f 7(Qd.) is known only for d < 6 and for d = 2k — 1 or d = 2k, see [15, p. 90]. Using the second representation of EH(s,t) it follows immediately that 7(EH(s,t)) < 2s^(Qt) + 2*7(Qs). With a little effort we can say a bit more: Proposition 2.2 If s,t > 1 and s 1 andu,v € V(EH(s,t)), then Proof. Note first that d,(u,v) > H(u,v) because EH(s,t) is a spanning subgraph of Qs+t+1 and dQs+t+1(u,v) = H(u,v). Suppose first that u.q = vq = 0 and u,p 1 = vp\. Then u and v belong to the same subgraph Qs of EHo(s,t) and hence d(u,v) < H(u,v). Thus d(u,v) = H(u,v). Analogously we get the same conclusion when u,q = vq = 1 and us+p.t+1 = I's+t-.t+i- Let. next uq / vq and assume without loss of generality that u.q = 0 and vq = 1. Then a u, v-pat.h of length H(u, v) can be constructed as follows. First change one by one the bits of u between u,s+t and ut+1 in which u differs from v. Then change the rightmost bit to 1, and finally change the remaining bits in which u differs from v. Hence in all these cases we have d(u,v) = H(u,,v). Assume now that u.q = vq = 0 and Uf. 1 / vp.i- Then u and v belong to different copies of Qs from EHo(s,t). Hence any u, v-path necessarily contains at least two matching edges between EHo(s,t) and EHi(s,t). Then it follows that d(u,v) > H(u,, v) + 2. We can find a u, v-path of length H(u, v) + 2 as follows: change one by one H(u,, v) + 2, u0 = v0 = 0, ut: 1 / vpi, or Uq = Vq = l,Us+t:t+l / Vs+pt+l] H(u,v), otherwise. the bits of u between us+t and ut+i in which u differs from v, then change the rightmost bit to 1, change the remaining bits in which u differs from v, and finally change the rightmost bit to 0. We conclude that d(u,v) = H(u,v) + 2. The case uq = vq = 1 and Us+t-.t+1 / vs+t:t+i is treated analogously. □ Theorem 3.2 If s,t> 1, then W(EH(s, t)) = {s + t + 3)22(i+i) - 22s+t - 2s+2t. Proof. By Lemma 3.1, the contribution of a pair {u,v} € (V{EH{s,t))^ to W(EH(s,t)) is either H(u, v) or H(u, v) + 2. Thus W(EH(s, t)) is the sum of W{Qs+t+1) and twice the number of pairs of vertices {u, v} with d(u,v) = H(u,v) + 2. Consider first pairs with uq = vq = 0 and upi / vp\. In the subcase when us+t:t+i = I's+t-.t+i, there are 2s possible substrings for the first s coordinates and hence the number of (unordered) pairs of vertices with uq = vq = 0, upi / vp.i, and us+p.t+1 = vs+t:t+i, is J2' If on the other hand us+pt+1 / Vs+t:t+i, we have (22) pairs with respect to the first s coordinates and (22) for the consecutive t coordinates. As such pairs can be combined in two ways, the number of such (unordered) pairs of vertices is '2S\ /2iN 2. 2 J \ 2 Similarly, the number of pairs {u, v} with uq = vq = 1 and us+p.t+1 / vs+t:t+i is equal to 22><2;)e; It, is well-known (cf. [12, Exercise 19.3]) that W(Qs+t+1) = (s +t + l)22^+i). Putting all this together we obtain that . (2S\ ^ . , /2S\ (2iN which, after a routine computation, reduces to the claimed expression. □ W(EH(s,t)) = (s + t + 1)22^ + 2 ((2)^ + (2j)2i + 4(:2 ) The average distance n(G) of a graph G is defined with KG) = ^y W(G) • We note that some authors prefer to define the average distance as 2W(G)/\V(G)\2. The definitions are almost equivalent and are in fact equivalent in the asymptotic sense, which we consider next. Corollary 3.3 lim KEH(s,t)) = lim MOd) = 1 s,i-S-oo S + t + 1 d—S-oo d 2 Proof. Using Theorem 3.2 we find that W(EH(s,t)) 1 W{Qs+t+1) s + t + 1 (s + i + 3 - 2_s - 2_i) , hence limSit_).00 = limSit_).00 • For the latter limit we have 1, then J (s+t+i r-, ; + (r-2>. "« = <>■ Proof. Assume vo = 0 and d(u, v) = r (0 < r < s +1 + 2). We count the number of u according to the three cases. Case 1: uq = 0, Uf.i = Vt-.i- By Lemma 3.1, there are r different bits between us+t:t+1 and vs+t:t+i- The number of u is . Note that r < s in this case. Case 2: uq = 0, Uf.i / Vf.i- By Lemma 3.1, there are r — 2 different bits between us+t:l and tVi-fci- Note that Ut:l / Vf.i and r > 3. The number of u is (^2) ~~ ir-2)- Case 3: uq = 1. By Lemma 3.1, there are r — 1 different bits between us-\~t:i and vs+t:i- The number of «* c;^)- Combining the above three cases we conclude that BEH{s,t)Ar) = (*) + ( We proceed analogously when vo = 1. □ 's + t\-( s \ + (s + t\ - (s + t + A , M _ ( s ,r — 2/ [r-2 [r - 1J [ r-1 ) [r [r - 2 We conclude the section by noting that Theorem 3.4 yields another proof of Theorem 3.2. The computations are rather technical, so we state only the key steps. If vo = 0, the total distance of v is s+i+2 Y^ d{u,v) = Y r ' BEH(s,t)Ar) ueV(EH(s,t)) r= 1 s+t+2 = r s + t + n /s\ _ / s r — 1 / \r) \r — 2 r= 1 = (s + i + 3)2i+i - 2i+1. Analogously, if vo = 1, then the total distance of v is (s + t + 3)2s+t — 2i+1. The number of vertices with vo = 0 (or vo = 1) is 2s+t. Hence, the Wiener index of EH(s,t) is 2s+t[(s + t + 3)2i+i - 2i+1 + (s + t + 3)2i+i - 2t+1}/2 = (s+t+_22i+i-2i+2i. 4 Additional properties Recall that the eccentricity ecc(u) of a vertex u € V(G) is the maximum distance between u and the vertices of G. The radius rad(G) and the diameter diam(G) of G are the minimum and the maximum eccentricity in G, respectively. From Lemma 3.1 we can also determine the eccentricity of vertices of EH(s, t). Let u be an arbitrary vertex, then its binary complement u is the unique vertex with respect to u with the property H(u,u) = s+i+1. By Lemma 3.1 we infer that d(u,u) = s+i+1. On the other hand, the lemma implies that d(u,u') = s +1 + 2, where vf is the vertex obtained from u by complementing U®. Moreover, using Lemma 3.1 again, we also observe that the vertex u' is the unique vertex to u such that ecc(u) = d(u,u'). We collect these facts into the following result, where the average eccentricity (cf. [13]) is defined in the natural way. (We note that the diameter of EH(s,t) was earlier determined in [23, Theorem 6].) Proposition 4.1 If u € V(EH(s,t)), then ecc(u) = s + t + 2 and hence the average eccentricity of EH(s,t) is s + t + 2. Moreover, every vertex has a unique antipodal vertex. Corollary 4.2 Ifs,t > 1, then diam(EH(s, t)) = rad(EH(s,t)) =s + t + 2. This should be compared with the fact that diam(Qs+t+i) = rad(Qs+i+i) = s+i+1. Hence again the exchanged hypercubes keep these fine properties of hypercubes. The Cartesian product GDH of graphs G and H is the graph with vertex set V(G) x V(H), vertices (g,h) and (g',h') being adjacent whenever gg' € E(G) and h = h', or g = g' and hh' € E(H). For more information on this graph operation see [12], For our purpose it is essential to recall that Qd, can be represented as the d-fold Cartesian product of K-2- Hence hypercubes are in a way the simplest possible Cartesian product graphs. A graph that cannot be represented as the Cartesian product of graphs on at least two vertices, is called prime (with respect to the Cartesian product). We conclude this note with the following results that contrasts exchanged hypercubes from hypercubes. Proposition 4.3 Ifs,t> 1, then EH(s,t) is a prime graph. Proof. Consider vertices u, = 00 ... 00 and v = 00 ... 01. Clearly, uv € E(EH(s, t)). The open neighborhood N(u) of u, is {v,u^t+1\ ... where = 1 for t + 1 < i < s + t, and u^ = 0 for t + 1 < i < s + t, 0 < j < s + t, j / i. Similarly, N(v) = {u, ..., v^}, where v^ = v^ = 1 for 1 < i < t, and v^ = 0 for 1 < i < t, 1 < i < s + i, j / i. It follows that if x € N(u) — {v} and y € N(v) — {t/,}, then d(x,y) = 3. Consequently, the edge uv is contained in no 4-cycle of EH(s,t). Since in the Cartesian product of two nont.rivial graphs every edge is contained in at least one 4-cycle, the result is proved. □ 5 Concluding remarks In this paper we have obtained several properties of exchanged hypercubes with respect to the distance function. Another closely related class of cubes studied in the literature is formed by dual-cubes Dn, n > 1. These cubes were by now well studied, see for instance [1, 3, 21, 22], Here we follow the notation used in [1], As it turns out, Dn is 00 1—1 o CM CO isomorphic to EH(n — 1 ,n — 1). Hence all our results can be directly applied to the dual-cubes. For instance: Corollary 5.1 If n > 1, then W{Dn+l) = (2n + 3)24ra - 23ra+1. CM Dual-cubes are vertex-transitive graphs. For such graphs G the surface area is C/3 independent of a selected vertex u, hence the notation Bc^r) can be simplified to bJO Bg{t). Then we have: Corollary 5.2 If n > 1, then BDn+1(r) = + ("+1) - (^J). •N Proof. Apply Theorem 3.4 together with the facts that Dn+i is isomorphic to EH(n, n) and that C;)-C¿2) = (T) " «)• ° Very recently dual-cubes Dn were generalized to dual-cube-like networks DCn in [1], DCn consists of 2™ disjoint copies of Qn-i- In addition, it contains a perfect matching, where the endpoints belong to different copies of Qn-i, and between any two copies of Qn-i there is at most one edge of the perfect matching. This generalization of dual-cubes to dual-cube-like networks can be naturally extended to generalize extended hypercubes to extended hypercube-like networks. We think it would be worth studying CM the extended hypercube-like networks. CM Acknowledgements ¡5 This work was supported in part by ARRS Slovenia under the grant. P1-0297, the China-Slovenia. bilateral grant. BI-CN/11-13-001, and the national natural science foundation of China. 11101378. References [1] A. Angjeli, E. Cheng, L. Liptak, Linearly many faults in dual-cube-like networks, Theoret,. Comput. Sci. 472 (2013) 1-8. CD [2] H. Braun, F.C. Stephan, On optimizing diameter and average distance of directed interconnected networks, IEEE Trans. Comput,. 42 (1993) 353-358. W [3] J.-C. Chen, C.-H. Tsai, Conditional edge-fa.ult.-t.olera.nt. Hamiltonicit.y of dual-cubes, Inform. Sci. 181 (2011) 620-627. •T—I 00 1—1 o CO 4J CO M 2 00 0 o 1 CO ^ CO CO CO CD $H CD CO u a CD U [4] Y.W. Chen, A comment on "The exchanged hypercube", IEEE Trans. Parallel Distrib. Syst. 18 (2007) 576. [5] B. Cheng, J. Fan, X. Jia, J. Jia, Parallel construction of independent spanning trees and an application in diagnosis on Mobius cubes, J. Supercomput. (2013) DOI: 10.1007/ s11227-013-0883-1. [6] E. Cheng, K. Qiu, Z. Shen, On the surface areas and average distances of meshes and tori, Parallel Process. Lett. 21 (2011) 61-75. [7] E. Cheng, K. Qiu, Z. Shen, On the surface area of the augmented cubes, J. Supercomput. 61 (2012) 856-868. [8] A.A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (2001) 211-249. [9] A.A. Dobrynin, I. Gutman, S. Klavzar, P. Zigert, Wiener index of hexagonal systems, Acta Appl. Math. (2002) 247-294. [10] J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, J. Combin. Theory Ser. B 97 (2007) 1074-1076. [11] N. Graham, F. Harary, The number of perfect matchings in a hypercube, Appl. Math. Lett. 1 (1988) 45-48. [12] R. Hammack, W. Imrich, S. KlavZar, Handbook of Product Graphs, Second Edition, CRC Press, Boca Raton, FL, 2011. [13] A.M. Hinz, D. Parisse, The average eccentricity of Sierpinski graphs, Graphs Combin. 28 (2012) 671-686. [14] N. Imani, H. Sarbazi-Azad, S.G. Akl, Some topological properties of star graphs: The surface area and volume, Discrete Math. 309 (2009) 560-569. [15] W. Imrich, S. Klavzar, D.F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Products, A K Peters, Wellesley, 2008. [16] J.-S. Kim, S.W. Kim, E. Cheng, L. Liptak, Topological properties of folded hyperstar networks, J. Supercomput. 59 (2012) 1336-1347. [17] S. Klavzar, Structure of Fibonacci cubes: a survey, J. Comb. Optim. 25 (2013) 505-522. [18] S. Klavzar, M.J. Nadjafi-Arani, Wiener index versus Szeged index in networks, Discrete Appl. Math. 161 (2013) 1150-1153. [19] C.-N. Kuo, H.-H. Chou, N.-W. Chang, S.-Y. Hsieh, Fault-tolerant path embedding in folded hypercubes with both node and edge faults, Theoret. Comput. Sci. 475 (2013) 82-91. 00 [20] X.-J. Li, J.-M. Xu, Generalized measures of fault tolerance in exchanged hypercubes, Inform. Process. Lett. 113 (2013) 533-537. [21] Y. Li, S. Peng, Dual-cubes: a new interconnection network for high-performance computer clusters, in: Proceedings of the 2000 International Computer Architecture, 2000, pp. 51-57. +-> [22] Y. Li, S. Peng, W. Chu, Efficient collective communications in dual-cube, J. Su-percomput. 28 (2004) 71-90. M [23] P.K.K. Loh, W.J. Hsu, Y. Pan, The exchanged hypercube, IEEE Trans. Parallel Distrib. Syst. 16 (2005) 866-874. [24] M. Ma, B. Liu, Cycles embedding in exchanged hypercubes, Inform. Process. Lett. 110 (2009) 71-76. i—l [25] M. Ma, The connectivity of exchanged hypercubes, Discrete Math. Algorithms Appl. 2 (2010) 213-220. 0 [26] M. Ma, L. Zhu, The super connectivity of exchanged hypercubes, Inform. Process. Lett. 111 (2011) 360-364. [27] I. Pesek, M. Rotovnik, D. Vukicevic, J. Zerovnik, Wiener number of directed graphs and its relation to the oriented network design problem, MATCH Commun. Math. Comput. Chem. 64 (2010) 727-742. 1 [28] S. Wang, G. Zhang, K. Feng, Fault tolerance in k-ary n-cube networks, Theoret. Comput. Sci. 460 (2012) 34-41. [29] X. Wang, J. Fan, X. Jia, S. Zhang, J. Yu, Embedding meshes into twisted-cubes, Inform. Sci. 181 (2011) 3085-3099. CO CO CD $H CD CO $H a 13 Jh