IMFM Institute of Mathematics, Physics and Mechanics JADRANSKA 19, 1000 LJUBLJANA, SLOVENIA Preprint series Vol. 48 (2010), 1121 ISSN 2232-2094 ON THE DOMINATION NUMBER AND THE 2-PACKING NUMBER OF FIBONACCI CUBES AND LUCAS CUBES Aline Castro Sandi Klavzar Michel Mollard Yoomi Rho Ljubljana, August 02, 2010 On the domination number and the 2-packing number of Fibonacci cubes and Lucas cubes co 2 CSI Aline Castro Institut Fourier, UJF, 100, rue des Maths BP 74, 38402 St Martin d'Heres Cedex, France e-mail: aline.castro@ujf-grenoble.fr Sandi Klavzar Faculty of Mathematics and Physics University of Ljubljana, Slovenia and Faculty of Natural Sciences and Mathematics University of Maribor, Slovenia e-mail: sandi.klavzar@fmf.uni-lj.si Michel Mollard Institut Fourier, UJF - CNRS, 100, rue des Maths BP 74, 38402 St Martin d'Heres Cedex, France e-mail: michel.mollard@ujf-grenoble.fr i Yoomi Rho* Department of Mathematics CSI University of Incheon, Korea e-mail: rho@incheon.ac.kr £ CO CO CO July 16, 2010 Abstract Let rn and An be the n-dimensional Fibonacci cube and Lucas cube, respectively. The domination number 7 of Fibonacci cubes and Lucas cubes is studied. In particular it is proved that 7 (An) is bounded below by Ln—3T , where Ln is the n-th Lucas number. The 2-packing number p of these cubes is also studied. It is proved that HiLni_i p(rn) is bounded below by 23 2 and the exact values of p(rn) and p(An) are obtained for n < 10. It is also shown that Aut(rn) ~ Z3. cd Key words: Fibonacci cubes; Lucas cubes; domination number; 2-packing number; automorphism group; computer search * Corresponding author a CD u Oh 2 CSI o CSI i 1 Introduction Fibonacci cubes form a class of graphs introduced because of their properties applicable for interconnection networks [5]. Lucas cubes [10] are subgraphs of Fibonacci cubes in which certain "non-symmetric" vertices are removed. In this way we get graphs with more symmetries, a fact that will be further justified in this paper. Both classes of cubes have been considered from various points of view, see [1, 2, 3, 8, 11, 13]. CO In this paper we study Fibonacci cubes and Lucas cubes from the viewpoint of domi- nation and packing. While searching for (vertex) subsets of a graph (like dominating sets) it is useful to know symmetries of the graph, hence we first describe automorphism groups of these graphs in Section 2. In Section 3 we study the domination number of Fibonacci cubes as initiated in [12], and also investigate that of Lucas cubes. We first give some connections between the domination number of Fibonacci cubes and Lucas cubes and construct dominating sets for 9-dimensional cubes. Then we obtain a lower bound on the domination number of Lucas cubes. A graph invariant closely related to the domination number is the 2-packing number, which is the topic of Section 4. We first obtain an exponential (in terms of the dimension) lower bound on the 2-packing number of the Lucas cubes which is a natural lower bound for the Fibonacci cubes. Combining computer search with some arguments the exact values for the 2-packing number of both classes of cubes up to and including dimension 10 are obtained. In the rest of this section we define the concepts needed in this paper. For a connected graph G, the distance dG(u,v) (or d(u,v) for short) between vertices u and v is the usual shortest path distance. Let n > 1. A Fibonacci string of length n is a binary string bib2 .. .bn with bi • bi+i = 0 for 1 < i < n. In other words, Fibonacci strings are binary strings that contain no consecutive 1's. The Fibonacci cube rn is the subgraph of Qn induced by the Fibonacci strings of length n. For convenience we also set To = Ki. A Fibonacci string bib2 .. .bn is a Lucas string if bi • bn = 0. The Lucas cube An is the subgraph of Qn induced by the Lucas strings of length n. We also set A0 = Ki. It is well-known (cf. [5]) that \V(rn)| = Fn+2, where Fn are the Fibonacci numbers: F0 = 0, Fi = 1, Fn = Fn-i + Fn-2 for n > 2. Similarly, \V(An)\ = Ln, see [10], where Ln are the Lucas numbers: L0 = 2, Li = 1, Ln = Ln-i + Ln-2 for n > 2. For 0 < k < n, let rnk be the set of vertices of rn that contain k 1's. Hence rn k is the set of vertices of rn at distance k from 0n. An,k is defined analogously. In particular, rn,o = An,0 = {0n} and i = An,i = {10n-i, 010n-2,..., 0n-i1}. If uv e E(rn), where u e rn,k and v e rn , k-i (k > 1), then we say that v is a down-neighbor of u and that u is an up-neighbor of v. The same terminology again applies to Lucas cubes. For a binary string b = bib2 .. .bn, let b be the binary complement of b and let bR = bnbn-i.. .bi be the reverse of b. For binary strings b and c of equal length, let b + c denote their sum computed bitwise modulo 2. For 1 < i < n, let ei be the binary string of length n with 1 in the i-th position and 0 elsewhere. According to this notation, rn,i = An, i = {ei,e2,..., en}. Let G be a graph. Then D Q V(G) is a dominating set if every vertex from V(G) \ D is a cd co CD u CD adjacent to some vertex from D. The domination number y(G) is the minimum cardinality of a dominating set of G. A set X C V(G) is called a 2-packing if d(u, v) > 2 for any different vertices u and v of X. The 2-packing number p(G) is the maximum cardinality of a 2-packing of G. It is well known that for any graph G, 7(G) > p(G), cf. [6]. Finally, the automorphism group of a graph G is denoted by Aut(G). For instance, Aut(Cn) = D2n, where Cn is the n-cycle and D2n is the dihedral group on n elements. Recall that D2n can be represented as (x,y | x2 = 1,yn = 1, (xy)2 = 1). co 2 Automorphism groups 2 In this section we determine the automorphism groups of Fibonacci cubes and Lucas cubes. Let n > 1 and define the reverse map r : rn ^ rn with: r(bib2 ...bn) = bR = Mn-i •••bi . (1) It is easy to observe that r is an automorphism of rn. We are going to prove that r is the only nontrivial automorphism of rn. For this sake, the following lemma is useful. Lemma 2.1 Let n > 3 and k > 2. Then u,v £ rnk have different sets of down-neighbors. ^ Proof. Since u,v £ rn,k, d(u,v) > 2. We distinguish two cases. Suppose first d(u,v) = 2 and let u and v differ in positions i and j. Since u,v £ rn,k, we may assume without loss of generality that ui = vj = 1 and uj = vi = 0. Moreover, u and v agree in all the other positions. Since k > 2, there exists an index £ = i,j such that ue = ve = 1. Then u + ee is a down-neighbor of u but not a down-neighbor of v. Assume now d(u,v) > 3. Let i be an arbitrary index such that ui = vi. We may assume that ui = 1. Then u + ei is a down-neighbor of u but not of v. □ £ Theorem 2.2 For any n > 1, Aut(rn) ~ Z2. Proof. The assertion is clear for n < 2, hence assume in the rest that n > 3. Let a £ Aut(rn). Since 0n is the only vertex of degree n, a(0n) = 0n. Therefore, a maps rn>1 onto rn,i. Let ^ = {10n-i, 0n-11} and r^ = rn,i \ rn,1. Since 10n-i and 0n-11 are the only vertices of degree n — 1, a maps rn 1 and Tn 1 onto themselves. We distinguish two cases. hh Case 1: a(10n-i) = 10n-i. Then, because a maps rn,1 onto r'ni1, we have a(0n-11) = 0n-11. Among the vertices of rn 1, only 010n 2 has no common up-neighbor with 10n 1. Therefore, a(010n 2) = 010n-2. In turn, among the remaining vertices of r"n1, only 0010n-3 has no common up-neighbor with 010n-2. Therefore a(0010n-3) = 0010n-3. By proceeding with the same argument, a fixes Tn 1 pointwise and hence fixes rn , 1 pointwise. Now apply Lemma 2.1 and induction on k to conclude that a fixes rn, k pointwise for all k. Therefore a = id in this case. a cd Case 2: a(10n-1) = 0n-11. Now a(0n-11) = 10n-1. Among the vertices of Tn1, only 010n-2 has no common up-neighbor with 10n 1. Thus a(010n 2) = 0n 210, which is the only element of r''n 1 with no common up-neighbor together with a(10n-1) = 0n-11. By proceeding with the same argument, a reverses all the elements of Tn1, that is, av" = rr« and consecutively arn 1 = rrn1. By Lemma 2.1 and induction on k, the Therefore a = r in this case. □ CSI o Let n > 1. An equivalent way to define An is that it is the subgraph of Qn induced on all the binary strings of length n that have no two consecutive 1's in circular manner. This definition is more symmetric than the definition of the Fibonacci strings, so it is reasonable to expect that Aut(An) is richer than Aut(rn). This is indeed the case. Define p : An ^ An by ^(M2 ■■■bn) = bnb1 . . . bn-1 ■ (2) By the above remark it is clear that p £ Aut(An). Zagaglia Salvi [14] proved that the automorphism groups of the Lucas semilattices are the dihedral groups. The arguments that determine the automorphism group of the Lucas cubes are in a way parallel to the arguments from [14], hence we next give just a sketch of them. Note first that Lemma 2.1 with the same proof applies to Lucas cubes as well. Let a £ Aut(An). Suppose that for some a,b £ {0,1,...,n — 1}, a(10n-1) = 0a10n-a-1 and a(0n-11) = 0610n-6-1, where computations are mod n. Then either b = a — 1or b = a + 1 because a(10n-1) and a(0n-11) cannot have a common up-neighbor. When b = a — 1 we get a = pa and in the other case a = pa+1 ◦ r. We conclude that Aut(An) is generated by r and pa for 0 < a < n — 1, and hence: CO Theorem 2.3 For any n > 3, Aut(An) ~ D2n. C^ 3 The domination number CO In this section we consider the domination number of Fibonaci and Lucas cubes. We first interrelate their domination numbers. Then we discuss exact domination numbers for small dimensions. The section is conluded by establishing a general lower bound on the domination number of Lucas cubes. Proposition 3.1 Let n > 4, then (i) Y(An) < Y(rn-1)+ Y(rn-3) , (ii) Y(An) < Y(rn) < Y(An) + Y^n-4) ■ .cd Proof. (i) V(An) can be partitioned into vertices that start with 0 and vertices that start with 1. The latter vertices are of the form 10 ■ ■ ■ 0 and hance can be dominated by y(rn-3) vertices while the former vertices can be dominated by y(rn-1) vertices. (ii) Let D be a minimum dominating set of rn and set W D' = {u | u is a Lucas string from D} U {0b2 ■ ■ ■ bn-10 | 1b2 ■ ■ ■ bn-11 £ D} ■ O 4j co 2 0 o 1 CO ^ CO CO co cd $h CD co A vertex 1b2 • • • bn-11 dominates two Lucas vertices, namely 0b2 ••• bn-11 and 1b2 • • • bn-10. Since these two vertices are dominated by 0b2 • • • bn-10, we infer that D is a dominating set of An. It follows that 7(An) < 7(rn). A dominating set of An dominates all vertices of rn but the vertices of the form 10b3 • • • bn-201. These vertices can be dominated by 7(rn-4) vertices. □ It can be easily checked that Proposition 3.1 (i) holds for any n > 2, and that the first inequality of Proposition 3.1 (ii) holds for any n > 0. Pike and Zou [12] obtained exact values of 7(rn) for n < 8, see Table 2. By computer search they found 509 minimum dominating sets of Tg. Following their approach we have computed the domination numbers of An, n < 8, see Table 2 again. Hence the smallest Fibonacci cube and Lucas cube for which the domination numbers are not known are rg and Ag. Since 7(rn) < 7(rn-1)+ Y(rn-2), it follows that 7(rg) < 20, cf. [12, Lemma 3.1]. Since for an exhaustive search too much computer time would be needed, we have used a local search procedure in order to find a smaller dominating set: to get a new dominating set we have replaced one or more vertices with another vertex. In this way we were able to construct a dominating set of rg of size 17 given on the left-hand side of Table 1. Similarly we have found a dominating set of Ag of order 16 given on the right-hand side of Table 1. Hence: Proposition 3.2 Y(rg) < 17 and 7(Ag) < 16. We conjecture that Y(rg) = 17 and y(A9) = 16 hold. 010000000 100100000 010100000 001000100 000010010 000001010 000001001 101001000 101000010 100010100 100000101 001010001 000101001 000101010 000100101 101010001 010010101 000000000 000010000 000000100 000100100 000100010 000010010 101000010 100101000 010100001 010001010 001001001 101010100 101001010 010101001 010010101 001010101 u a CD u Table 1: A dominating set of rg and a dominating set of Ag 2 o £ CO CO u a cd u Pike and Zou [12] also proved that for any n > 4, Fn+2 — 3 o 7(rn) > n2 (N We next prove a parallel lower bound for the domination number of Lucas cubes. For this sake we first consider degrees of some specific vertices in Lucas cubes. Recall that An>1 is the set of all the vertices with exactly one 1. In addition, set An,2 = {OnOlO—3 | 0 < a < n — 1} , where we again compute by modulo n. Hence An 2 is the subset of An,2 consisting of the Lucas strings containing (in circular manner) 101 as a substring. Lemma 3.3 Let n > 7. Then for the Lucas cube An, the followings hold. (i) The vertex 0n is the only vertex of the maximum degree n. (ii) The vertices of An>1 have degree n — 2. (iii) Among the vertices with at least two 1's, only the vertices of A'n2 have degree n — 3 and all the other vertices have degree at most n — 4. Proof. (i) and (ii) are clear. (iii) Let u £ An,k for some k > 2. Then u has k down-neighbors. The up-neighbors of u are obtained by switching a bit 0 into 1. Let i1 2 for all 1 < j < k. Let Ij = {ij — 1, ij + 1} be the set of the positions which are adjacent to ij for each 1 < j < k and let I = (J 1 = 0 if Ij — j'\ > 2, therefore by pigeon-hole principle, II| > k. The equality holds if and only if Ij Ij+1 = 0 for all 1 < j < k, which occurs if and only if ij+1 = ij +2 for all 1 < j < k, which is in turn true if and only if n is even and k = n. But in this case, deg(u) = n < n — 4 as n > 8. In the other cases, \I\ > k + 1 and hence deg(u) < n — k — 1. If k > 3, then deg(u) < n — 4. Assume k = 2. Then deg(u) < n — 3, where the equality holds exactly when \I\ =3 and I^ I2 = 0 which means that u £ A'n 2. □ Lemma 3.4 Any l vertices from A'n 2 have at least l down-neighbors, that is, at least l neighbors in An, 1. CD Proof. For 1 < i < l, let Ai be the set of down-neighbors of vi £ A'n 2. Then \Ai\ = 2 for each i. Considering bits by modulo n, each vertex 0a10n_a_1 in An , 1 can be a down-neighbor of at most two vertices 0a1010n_a_3 and 0a_21010n_a_1, and hence at most two of v1,... ,vi. By pigeon-hole principle, the assertion is true. □ O 4j co 2 0 o 1 CO ^ CO CO co cd $h CD co j-h a CD U To establish the announced lower bound, we will apply the natural concept of over-domination, just as it is done in [12]. It is defined as follows. Let D be a dominating set of a graph G. Then the over-domination of G with respect to D is: ODG(D) = £ (degG(v) + 1) - (G)| • (3) veD Note that ODG(D) = 0 if and only if D is a perfect dominating set [9, 4], that is, a dominating set such that each vertex is dominated exactly once. Theorem 3.5 For any n > 7, y(An) > Ln — 2n n3 Proof. Let D be a minimum dominating set of An. Set D1 = Dn An>1 and D2 = Dn An 2, and let k = ID n An>1| and l = ID n A'n2l. Then clearly 0 < k,l < n. Note that the over-domination of G with respect to D can be rewritten as (4) OD(G)= ^ (|{v G D I d(u,v) < 1}| — 1) • uev (An) For a vertex u of An, set t(u) = |{v G D | d(u,v) < 1}| — 1. As D is a dominating set, t(u) > 0 for all u G V(An). We now distinguish two cases. Case 1: 0n G D. Combining Lemma 3.3 with Equation (3) we get OD(D) < (n + 1)+ k(n — 1) + l(n — 2) + (y(A„) — k — l — 1)(n — 3) — Ln = y(An)(n — 3)+2k + l + 4 — Ln • Also as t(u) > 0 for all u G V, Equation (4) implies OD(D) > t(0n) + t(v) > 2k • veDi Therefore Y(An) > Ln-l-4 n—3 > Ln-n-4 n— 3 Case 2: 0n G D. Again, combining Lemma 3.3 with Equation (3) we infer OD(D) < k(n — 1)+ l(n — 2) + (y(A„) — k — l)(n — 3) — Ln = y(An)(n — 3) +2k + l — Ln • Let A be the set of down-neighbors of D2. Then for u G D1 n A, t(u) > 1. By Lemma 3.4, |A| > l and hence |D1 P| A| > k + l — n. Therefore by Equation (4), OD(D) > t(v) > k + l — n. veDif] A Thus Y(An) > Ln-k-n n-3 > Ln-2n n-3 By Case 1 and Case 2, y(An) > Ln-2n n-3 □ O 4j co M < 0 o 1 CO ^ CO CO 4 The 2-packing number We now turn to the 2-packing number and first prove the following asymptotical lower bound. Lig n _1 Theorem 4.1 For any n > 8, p(rn) > p(An) > 22. Proof. Since for any n > 1, An is an isometric subgraph of rn, cf. [7], a 2-packing of An is also a 2-packing of rn. Therefore p(rn) > p(An). Let r,s > 1 and let X and Y be maximum 2-packings of Ar and As, respectively. Then {x0y | x £ X,y £ Y} is a 2-packings of Ar+s+1 of size p(As)p(As). It follows that p(Ar+s+i) > p(Ar)p(As). Set now k = |_lgnj. Then p(A2k) > p(A2k_i+1) > p(A2k_2)2. By repeatedly applying this argument we get p(An) > p(A2k) > p(A2k_2l )2 . When k is even, take l = k-2 to get p(An) > p(A4) k_3 k_3 k_3 l = to get p(An) > p(Ag)2 k_2 = 22 k_2 > 82 2 = 23x2 2 > 22 2 When k is odd, take □ Using computer we obtained the 2-packing numbers of rn and An for n < 10 given in Table 2. n 0 1 2 3 4 5 6 7 8 9 Y(rn) 1 1 1 2 3 4 5 8 12 <17 p(rn) 1 1 1 2 2 3 5 6 9 14 Y (An) 1 1 1 1 3 4 5 7 11 <16 p(An) 1 1 1 1 2 3 5 6 8 13 10 Table 2: Domination numbers and 2-packing numbers of small cubes Table 2 needs several comments. m cd u CD m u a CD U The computer search found exactly ten 2-packings of size 20 in r1o. This already implies that p(r10) = 20. Indeed, if r10 would contain a 2-packing of size 21, then it would contain twenty-one 2-packings of size 20. By exhaustive search with computer no 2-packing of size 19 in A10 was found, hence p(Aio) = 18. There is only one (up to isomorphisms of the graphs considered) maximum 2-packing of A5, A6, A7, Ag, as well as r6. There are two non-isomorphic 2-packings of maximum cardinality of rg, they are presented in the first two columns of Table 3. k2 o o 4j m 2 0 o 1 CO ^ CO CO Since the reverse map given in (1) is an automorphism of Fibonacci cubes, the reverse of a 2-packing is also a 2-packing. Interestingly, the maximum 2-packing of rg shown on the left-hand side of Table 3, denoted X, is also invariant under the reverse map. That is, r(X) = X. Similarly, the shifts where p is given in (2) and i £ {1,..., n-1}, are automorphisms of Lucas cubes, hence they map 2-packings into 2-packings. Now consider the 2-packing of Ag shown on the right-hand side of Table 3, denote it Y. Then it can be checked that p3(Y) = Y. As a consequence, p6(Y) = Y. 000 001 010 010 100 000 000 100 101 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 100 000 100 010 001001 100 100 010 010 010 101 101010 010 001010 100 010 010 010 100 010 001 100 101001 000 001000 000 100 100 001 000 010 001010 001 010 000 101 010 010 000 010 100 010 010 101001 100 010 010 100 010 101 100 100 001 100 101010 101 000 100 1 0 1 0 0 1 0 0 1 100 100 100 000 010 001 000101001 001 000 010 001 000 101 010 001000 010 010 100 010 100 010 010 100 101 100 010 010 100 101010 1 0 1 0 0 1 0 0 0 101010 100 Table 3: Maximum 2-packings of rg and of Ag 5 Concluding remarks Based on the data from Table 2 we ask whether some of the followings are true. Problem 5.1 Is it true that (i) 7(rra) - p(rra) > 7(An) - p(An) for n > 0? (ii) 7(An) > P(rn) for n > 4? (iii) 7(An) < 7(rn-i) + 7(rn-s) - 1 for n > 6 ? co cd Jh CD co u a CD U Note that the last question, if it has an affirmative answer, reduces the bound of 7(An) in Proposition 3.1 (i) by 1. Moreover, in that case one can also ask whether 7(An) < 7(rn-i) + 7(rn-4) holds for n > 6. Acknowledgements This work was supported in part by the Proteus project BI-FR/08-09-PR0TEUS-002. The work of Sandi Klavzar was supported by the Ministry of Science of Slovenia under the grants P1-0297, the work of Yoomi Rho was supported by the National Research Foundation of Korea Grant founded by the Korean Government (NRF-2010-013-C00002). CSI o 2 2 References [1] Ernesto Dedo, Damiano Torri, and Norma Zagaglia Salvi. The observability of the Fibonacci and the Lucas cubes. Discrete Math., 255(1-3):55-63, 2002. [2] Joanna A. Ellis-Monaghan, David A. Pike, and Yubo Zou. Decycling of Fibonacci cubes. Australas. J. Combin., 35:31-40, 2006. [3] Petr Gregor. Recursive fault-tolerance of Fibonacci cube in hypercubes. Discrete Math., 306(13):1327-1341, 2006. [4] Hamed Hatami and Pooya Hatami. Perfect dominating sets in the Cartesian products of prime cycles. Electron. J. Combin., 14(1):#N8, 7 pp., 2007. [5] W.-J. Hsu. Fibonacci cubes—a new interconnection technology. IEEE Trans. Parallel Distrib. Syst., 4(1):3-12, 1993. [6] Wilfried Imrich, Sandi KlavZar, and Douglas F. Rall. Topics in Graph Theory. A K Peters Ltd., Wellesley, MA, 2008. [7] Sandi KlavZar. On median nature and enumerative properties of Fibonacci-like cubes. Discrete Math., 299(1-3):145-153, 2005. i [8] Sandi KlavZar and Petra Zigert. Fibonacci cubes are the resonance graphs of Fi- 00 bonaccenes. Fibonacci Quart., 43(3):269-276, 2005. CSI [9] Marilynn Livingston and Quentin F. Stout. Perfect dominating sets. Congr. Numer., 79:187-203, 1990. CO [10] Emanuele Munarini, Claudio Perelli Cippo, and Norma Zagaglia Salvi. On the Lucas cubes. Fibonacci Quart., 39(1):12-21, 2001. [11] Emanuele Munarini and Norma Salvi Zagaglia. Structural and enumerative properties of the Fibonacci cubes. Discrete Math., 255(1-3):317-324, 2002. [12] David A. Pike and Yubo Zou. The domination number of Fibonacci cubes. Manuscript, 2009. [13] Andrej Taranenko and Aleksander Vesel. Fast recognition of Fibonacci cubes. Algo-rithmica, 49(2):81-93, 2007. • [14] N. Zagaglia Salvi. The automorphism group of the Lucas semilattice. Bull. Inst. Combin. Appl, 34:11-15, 2002. Jh a CD