IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 51 (2013), 1190 ISSN 2232-2094 THE DOMINATION NUMBER OF EXCHANGED HYPERCUBES Sandi Klavžar Meijie Ma Ljubljana, August 23, 2013 2 o o» o The domination number of exchanged hypercubes Sandi Klavžar 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 O Abstract I 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. Lower and upper bounds on the domination number of exchanged hypercubes are proved which in particular imply that j(EH(2,t)) = 2i+1 holds for any t > 2. Using Hamming codes we also prove that 7(EH(s, 2k-l)) < (2s-2k)y(Qt) + 2t(i(Q-) + 1) holds for s > k > 3. CO Key words: interconnection network; hypercube; exchanged hypercube; domination number; Hamming code AMS Subj. Class.: 05C69, 68R10 1 Introduction Hypercubes form a fundamental model for parallel computers and interconnection networks, cf. [22, Chapter 7]. They have many fine properties that are essential for network efficiency, such as recursive decomposition, lots of symmetries, low regularity, and small diameter. Hypercubes also allow straightforward (local) routing and are Hamil-tonian. For more information on their fault tolerance with respect to the hamiltonicity 'J- ^ 1 CD 1 00 o CM CO CM see [19, 20] and references therein. Having all this in mind it comes with no big surprise that machines based on hypercubes have actually been implemented, see [22, p. 115] for the list of implementations. Interconnection networks often require a distribution of limited supply of resources and from this point of view various kinds of dominating sets serve as possible locations for placement of resources. For general aspects of the role of domination in complex networks see the book chapter [1]. Unfortunately, the exact domination number is known only for small dimensional hypercubes and two infinite families: y(Q3) = 2, 7(Q4) = 4, y(Q5) = 7, y(Qa) = 12, and y(Qn) = 2n-k for n = 2k - 1 or n = 2k, see [8]. In general, y(Qn) < 2n-3 for n > 7 [3]. For some variations of domination studied on hypercubes see [3, 7, 17], while for domination of closely related Fibonacci cubes see [4, 18]. Domination was also studied on other types of interconnection networks as for instance on toroidal meshes [21]. o Since domination is very difficult on hypercubes, they are not very appropriate when dealing with domination-type problems. In this note we instead study the domination number of exchanged hypercubes EH(s,t). This two-parametric family of graphs was proposed by Loh et al. [13] and constitute a variation of the hypercube networks with numerous appealing properties, see [15] for their bipancyclicity and [10, 14, 16] for CM their connectivity and super connectivity, important measures for the fault-tolerance 00 of networks. In the special case when s = t, the exchanged hypercubes coincide with the so-called dual-cubes, a class of hypercube-like networks studied in [2, 5, 11, 12]. We proceed as follows. In the next section we introduce the exchanged hypercubes, CO recall some of their properties, and define other concepts used in this note. Then, in Section 3, our results are presented. We prove several bounds on the domination number of exchanged hypercubes and deduce from them that if t > 2, then y(EH(2,t)) = 2t+1. This exact result appears appealing because, as we have noted above, the domination number of the usual hypercubes is an intrinsically difficult problem. Using the fact that Q2k-1 contains a perfect code (which is just a corresponding Hamming code) we also prove that y(EH(s, 2k - 1)) < (2s - 2k)y(Qt) + 2t(y(Q-) + 1) holds for s > k > 3. CD • i 2 Preliminaries & Graphs considered here are simple, finite, and connected. £ If n is a positive integer, then the n-dimensional hypercube (or n-cube, for short) Jh Qn is the graph with vertex set {0,1}", two vertices (strings) being adjacent if they differ in exactly one coordinate. Hypercubes are vertex-transitive graphs, hence all vertex-deleted subgraphs Qn - v, v e V(Qn), are isomorphic, we denote it with Q~. The distance between vertices u,v e V(Qn) is equal to the Hamming distance between u and v, denoted H(u,v), that is, the number of coordinates in which u and v differ. Exchanged hypercubes are spanning subgraphs of hypercubes. Let u = Ud-i ■ ■ ■ Uo e {0,l}d be a binary string, d > 1. If j > i, then we will use the notation uj-.i for the substring of u between Uj and Ui, that is, Uj-.i = Uj...Ui. For any integers s > 1 and t > 1, the exchanged hypercu.be EH(s,t) is the graph with the vertex set {0,l}i+i+1. Hence, if u e 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 t Vo, (ii) u0 = v0 = l,H(ut:i,vt:i) = 1, and us+t.t+i = vs+t.t+1, (iii) u0 = Vo = 0,H(us+t:t+i,vs+t:t+i) = 1, and ut: 1 = vt-.i. Clearly, EH(s,t) has 2i+i+1 vertices. If u e V(EH(s,t)) and u o = 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). The ratio of the number of edges in EH(s,t) to that of Qs+t+1 is 1/2 + l/(2(s +1 + 1)) [6]. If G is a graph, then D £ V(G) is a dominating set if every vertex of V(G) - D is adjacent to some vertex of D. The domination number 7(G) is the minimum cardinality of a dominating set of G. A dominating set D of G is a perfect code if any two vertices from D are at distance at least 3. Hence the closed neighborhoods of the vertices from a perfect code D partition the vertex of G, cf. [9, Theorem 4.1]. A matching of a graph G is a set of independent edges and a perfect matching is a matching M such that each vertex is an endpoint. of an edge from M. Finally, if X c V(G), then the closed neighborhood is Uus.y-^M) where N[it] is the closed neighborhood of u. 3 Results We begin with the following bounds: Theorem 3.1 If s, t > 1 and s 7(Qt), for otherwise Tj n together with the neighbors of the vertices from Ti-V{Qf}) that lie in would form a dominating set of order strictly smaller than 7{Qt). In addition, if i ± j, then Tj n Tj = 0 because a vertex from Tj - has exactly one neighbor in EH\(s,t). It follows that IA>£|7*|>2*7(Qt)-i= 1 Applying analogous arguments to EHo(s,t) we infer that |-D| > 2t^{Qs). This proves the lower bound. □ For another upper bound the following lemma will be useful. Lemma 3.2 If n > 3, then V(Qn) can be partitioned into 4 (pairwise disjoint) dominating sets. Proof. For n = 3, the partition {{000, 111}, {100,011}, {010,101}, {001,110}} does the job. We proceed by induction. Let n > 3 and let V(Qn) = UtiA) where each Di (1 < i < 4) is a dominating set of Qn, and U denotes the disjoint union of sets. For 1 < i < 4 set D'i = {0U : U 6 Di} U {1 u : U, 6 A} • Then it is straightforward to verify that each D[ is a dominating set of Qn+i and that V(Qn+1) = Vi1D'i. □ Proposition 3.3 If2 3, then l(EH(s, t)) < (2s - 4)7(Qt) + 24(7(Q~) + 1). Proof. Since t > 3, Lemma 3.2 guarantees the existence of a partition V(Qt) = U^i Di, where each Di is a dominating set of Qt. Since s >2, EHi(s,t) (defined in the proof of Theorem 3.1) contains the four i-cubes q\%\ 1 < i < 4. For any i, let D[ be the isomorphic copy of A in Q(ti}. For 5 < i < 2", let Di be a minimum dominating set of q\%\ and for 1 < i < 24, let D" be a minimum dominating set of (q!^ . Note that | Uti D\\ = 2l and that each vertex from U^i D[ is adjacent to exactly one vertex in a private copy of Q^ in EH0(s,t). It, follows that D = (l£i A') U (u?=i A") is a domination set, of EH(s,t). Since U A' i= 1 2s UA' i=5 UA i= 1 = 2i + (2i-4)7(Qt) + 2i7(^) IA = the result, follows. □ We are now ready for our key insight,. Theorem 3.4 Ift> 2, then ^(EH(2,t)) = 2t+1. Proof. Let, t = 2. Then ^(EH(2,2)) > 8 by Theorem 3.1. In Fig. 2 a, dominating set, of EH(2,2) of size 8 is shown, hence 7(EH(2,2)) = 8. 11101\ 01011 \ \oiooi / /11000 / oiion \ 01000 01100 J ■TToooo .00000 ooiooi^^ N^lOOOl / J T ooioi\ A, /00011 00111 / 10001 J f 1010l\ / eh( 2,2) Figure 2: A minimum dominating set, of EH(2,2) Let, t > 3. Then the lower bound 7(EH(s,t)) > 2t+1 again follows from Theorem 3.1. On the other hand, 7(EH(s,t)) < 2t+1 follows from Proposition 3.3 having in mind that s = 2 and 7(^2) = 1. □ In the proof of Proposition 3.3 we have partitioned the vertex set, of Qn into four dominating sets. If V(Qn) can be partitioned into more disjoint, dominating sets, the upper bound can be improved. This is not, possible for n < 5 as we can find out, from the exact domination numbers of these cubes. On the other hand, using Hamming codes this can be done in the following special case. Theorem 3.5 If s> k > 3, then l(EH(s, 2k - 1)) < (2s - 2fc)7(Qt) + 2<(7(QJ) + 1). Proof. Let k > 3. Let Do be an arbitrary perfect code of Q2fc-1- It is well-known that such a code exists, see [9], in fact, it is just a Hamming code of block length 2k -1. Let 1 < i < 2k - 1, denote the binary word of length 2k - 1 with 1 in the ith coordinate and with 0 in any other coordinate. For any i set Di = {u + e(i) : w e .Do} - We claim that A n Dj = 0 for any i ± j, 0 < i,j < 2k - 1. Note first that D0 n A = 0, because if u e Di, then there exists an x e Do such that u = x+e^ and hence H(u, x) = 1. Since for any other vertex y of Do we have H(x,y) > 3, we conclude that u t y. Let next u e Di and v e Dj, where i,j > 1 and i + j. Then u = x + e^ and v = y + e^ for some x,y e Do. Because H(x,y) > 3 it then follows that u t v. The mapping Qn ->■ Qn that changes a fixed coordinate in each of the vertices is an automorphism of Qn. Since an automorphism maps dominations sets onto dominating set, we infer that Di, 1 < i < 2k - 1, are dominating sets because Do is such. We now construct a dominating set of EH(s,2k - 1) similarly as in the proof of Proposition 3.3. Since s > k, there exist 2k cubes Q^-i' 1 - - 2k■ For any 1 < i < 2k - 1, let D[ be the isomorphic copy of Di in ^ and let D!2k be the isomorphic /2k) j copy of Do in Q)2k_r For 2 + 1 < i < 2s, let D\ be a minimum dominating set of and for 1 < i < 22k~1, let D" be a minimum dominating set of (q!^ . Then D = (l£i D[) u 1 A") is a domination set of EH(s, 2k-l) of order (2i-2fc)7(Qt) + 2i(7(Qj) + l). □ Acknowledgements 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. 00 1—1 o 00 4J CO M 2 o 0 o 1 00 ^ CO CO CO CD $H CD CO u a CD U References [1] N. Ananchuen, W. Ananchuen, M.D. Plummer, Domination in graphs, in: Structural Analysis of Complex Networks, Birkhauser/Springer, New York, 2011, 73104. [2] A. Angjeli, E. Cheng, L. Liptak, Linearly many faults in dual-cube-like networks, Theoret. Comput. Sci. 472 (2013) 1-8. [3] S. Arumugam, R. Kala, Domination parameters of hypercubes, J. Indian Math. Soc. (N.S.) 65 (1998) 31-38. [4] A. Castro, S. Klavzar, M. Mollard, Y. Rho, On the domination number and the 2-packing number of Fibonacci cubes and Lucas cubes, Comput. Math. Appl. 61 (2011) 2655-2660. [5] J.-C. Chen, C.-H. Tsai, Conditional edge-fault-tolerant Hamiltonicity of dual-cubes, Inform. Sci. 181 (2011) 620-627. [6] Y.W. Chen, A comment on "The exchanged hypercube", IEEE Trans. Parallel Distrib. Syst. 18 (2007) 576. [7] T. Dvorak, I. Havel, M. Mollard, On paths and cycles dominating hypercubes, Discrete Math. 262 (2003) 121-129. [8] F. Harary, M. Livingston, Independent domination in hypercubes, Appl. Math. Lett. 6 (1993) 27-28. [9] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998. [10] X.-J. Li, J.-M. Xu, Generalized measures of fault tolerance in exchanged hypercubes, Inform. Process. Lett. 113 (2013) 533-537. [11] Y. Li, S. Peng, Dual-cubes: a new interconnection network for high-performance computer clusters, in: Proceedings of the 2000 International Computer Architecture, 2000, 51-57. [12] Y. Li, S. Peng, W. Chu, Efficient collective communications in dual-cube, J. Su-percomput. 28 (2004) 71-90. [13] P.K.K. Loh, W.J. Hsu, Y. Pan, The exchanged hypercube, IEEE Trans. Parallel Distrib. Syst. 16 (2005) 866-874. [14] M. Ma, The connectivity of exchanged hypercubes, Discrete Math. Algorithms Appl. 2 (2010) 213-220. [15] M. Ma, B. Liu, Cycles embedding in exchanged hypercubes, Inform. Process. Lett. 110 (2009) 71-76. 00 [16] M. Ma, L. Zhu, The super connectivity of exchanged hypercubes, Inform. Process. Lett. 111 (2011) 360-364. CM [17] S.A. Mane, B.N. Waphare, On independent and (d,n)-domination numbers of hypercubes, AKCE Int. J. Graphs Comb. 9 (2012) 161-168. CM [18] D.A. Pike, Y. Zou, The domination number of Fibonacci cubes, J. Combin. Math. Combin. Comput. 80 (2012) 433-444. [19] A. Szepietowski, Hamiltonian cycles in hypercubes with 2n-4 faulty edges, Inform. Sci. 215 (2012) 75-82. < [20] V. Vukasinovic, P. Gregor, R. Skrekovski, On the mutually independent Hamiltonian cycles in faulty hypercubes, Inform. Sci. 236 (2013) 224-235. m CD $H CD m u a CD U [21] X. Xie, J.-M. Xu, Domination numbers of undirected toroidal mesh, Acta Math. Sin. (Engl. Ser.) 28 (2012) 453-462. [22] J.-M. Xu, Combinatorial Theory in Networks, Mathematics Monograph Series 26, Science Press, Beijing, 2013.