ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 12 (2017) 25-29
The parameters of Fibonacci and Lucas cubes*
Marko Milosevic
Faculty of Sciences and Mathematics, University ofNis, Serbia
Received 10 August 2015, accepted 27 December 2015, published online 21 March 2016
Motivated by the conjectures from Castro, et al. in 2011, in this paper we use integer programming formulations for computing the domination number, the 2-packing number and the independent domination number of Fibonacci cubes and Lucas cubes for n < 13.
Keywords: Fibonacci cubes, Lucas cubes, domination number, 2-packing number. Math. Subj. Class.: 05C69, 05C25
1 Introduction
Hypercubes form one of the most applicable classes of graphs with many appealing properties. The n-cube Qn is the graph whose vertices are all binary strings of length n, and two vertices are adjacent if they differ in exactly one position. The Fibonacci cubes were introduced as a model for interconnection networks [4, 2]. They offer challenging mathematical and computational problems, and admit a recursive decomposition into smaller Fibonacci cubes (see [5], [6], [8] for their structural properties). The Fibonacci cubes can be recognized in O(m log n) time (where n is the order and m the size of a given graph) [10]. The Lucas cubes [7] form a class of graphs closely related to the Fibonacci cubes, obtained by removing some vertices from the Fibonacci cubes.
Let Qn be the n-dimensional hypercube. A Fibonacci string of length n is a binary string bib2.. .bn with bi • bi+1 =0 for 1 < i < n. In other words, Fibonacci strings are binary strings that contain no consecutive ones. The Fibonacci cube rn, for n > 1 is the subgraph of Qn induced by the Fibonacci strings of length n. A Fibonacci string bib2... bn is a Lucas string if bi • bn = 0. In other words, Lucas strings are binary strings
*This work was supported by Research Grants 174010 and 174033 of Serbian Ministry of Education and Science.
E-mail addresses: aleksandari@gmail.com (Aleksandar Ilic), marko643@gmail.com (Marko Milosevic)
Aleksandar Ilic
Facebook Inc, Menlo Park, CA, USA
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
26
Ars Math. Contemp. 12 (2017) 37-50
that contain no consecutive ones circularly. The Lucas cube An, for n > 1 is the subgraph of Qn induced by the Lucas strings of length n. It is well-known that |V(T„)| = Fn+2, where Fn are the Fibonacci numbers: F0 =0, F1 = 1, Fn+1 = Fn + Fn-1 for n > 1. Similarly, |V(An)| = Ln for n > 1, where Ln are the Lucas numbers: L0 = 2, L1 = 1, Ln+1 = Ln + Ln-i for n > 1.
Let G be a graph. Set D C V(G) is a dominating set if every vertex from V(G) either belongs to D or is 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 two 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 holds Y(G) > p(G).
An independent set or stable set is a set of vertices in a graph, no two of which are adjacent. The independent domination number ¿(G) of a graph G is the size of the smallest independent dominating set (or, equivalently, the size of the smallest maximal independent set). The minimum dominating set in a graph will not necessarily be independent, but the size of a minimum dominating set is always less than or equal to the size of a minimum maximal independent set, y(G) < ¿(G).
Pike and Zou in [9] obtained a lower bound for the domination number of Fibonacci cube of order n and determined the exact value of the domination number of Fibonacci cubes of order at most 8. Castro et al. in [1] obtained upper and lower bounds for the domination and 2-packing number of Fibonacci and Lucas cubes. Furthermore, the authors obtained the exact values for Y(rn) and Y(An) for n < 9 and for p(rn) and p(An) for n < 10.
In this paper we use integer programming method to compute the exact values of the domination, 2-packing and independent domination number of Fibonacci and Lucas cubes for n < 13, which resolves the conjecture from [1].
2 Main results
For each subset of the vertex set S ç V(G) define
1 if i e S 0 if i e V \ S.
The neighborhood N(v) of a vertex v in a graph G is the induced subgraph of G consisting of all vertices adjacent to v and all edges connecting two such vertices. Let N [v] = N (v) U {v} denote the closed neighborhood of the vertex v.
The domination number of G can be formulated as the following 0 -1 integer programming problem:
n
y(G) = min ^ Xi	(2.1)
i=i
subject to
^ Xj > 1,	(2.2)
jeN [i]
Xi e {0,1}, for all 1 < i < n.	(2.3)
It is easy to see that the conditions (2.2) and (2.3) define dominating set S and vice versa [3]. For Fibonacci cube rn this formulation has Fn+2 variables and 2Fn+2 constraints,
A. Ilic & M. Milosevic: The parameters of Fibonacci and Lucas Cubes
27
while each condition from (2.2) contains at most n variables. For Lucas cube An this formulation has Ln variables and 2Ln constrains, while each condition from (2.2) contains at most n variables.
The 2-packing number of G can be formulated as the following 0 - 1 integer programming problem:
n
p(G) = max X>i	(2.4)
i=i
subject to
^ xj < 1,	(2.5)
jew [i]
xi G {0,1}, for all 1 < i < n.	(2.6)
We will prove that the conditions (2.5) and (2.6) define 2-packing set S and vice versa. Let S be a 2-packing set. Since S does not contain two vertices on distance 1 or 2, for each v G V(G) there is at most one vertex from the closed neighborhood N[v] which belongs to S. Assume now that the set S satisfies the condition (2.5) and let u and v be two vertices from S on distance 2. In that case for the shortest path vwu, we have J2jeN[w] xj > 2, which is impossible. Therefore, S is a 2-packing set.
The independent domination number G can be formulated as the following 0 -1 integer programming problem:
n
i(G) = min ^ xi	(2.7)
i=i
subject to
^ xj > 1,	(2.8)
jew [i]
(n - 1)xi + xj < n - 1,	(2.9)
jew (i)
xi G {0,1}, for all 1 < i < n.	(2.10)
The conditions (2.8) and (2.10) define domination set S, while the condition (2.9) ensures the independence. For xi =0 we have always true (i) xj < n - 1, while for xi = 1 we have J2jeN(i) xj < 0 which is equivalent to 2jeN[i] xj = 1. This proves that the formulation is correct. For Fibonacci cube rn this formulation has Fn+2 variables and 3Fn+2 constraints, while each conditions from (2.8) and (2.9) contain at most n variables. For Lucas cube An this formulation has Ln variables and 3Ln constrains, while each condition from (2.8) and (2.9) contain at most n variables.
The tests were performed on the Intel Core 2 Duo T5800 2.0 GHz with 2 GB RAM running the Linux operating system and using CPLEX 8.1. The results are summarized in Tables 1 and 2. In Tables 3 and 4 we give some examples of dominating sets and 2-packing sets that were obtained during the computation of these values.
These results resolve the conjecture from [1] and support Problem 5.1 for n < 12.
28
Ars Math. Contemp. 12 (2017) 37-50
n	1	2	3	4	5	6	7	8	9	10	11
|V (r„)|	2	3	5	8	13	21	34	55	89	144	233
I e (r„)|	1	2	5	10	20	38	71	130	235	420	744
7(r„)	1	1	2	3	4	5	8	12	17	25	
p(r„)	1	1	2	2	3	5	6	9	14	20	29
i(r„)	1	1	2	3	4	5	8	12	19	26	
Table 1: Parameters of small Fibonacci cubes.
n	1	2	3	4	5	6	7	8	9	10	11	12
|V(An) I	1	3	4	7	11	18	29	47	76	123	199	322
IE (An) |	0	2	3	8	15	30	56	104	189	340	605	1068
Y(An)	1	1	1	3	4	5	7	11	16	23	35	
P(An)	1	1	1	2	3	5	6	8	13	18	26	38
i(An)	1	1	1	3	4	5	8	11	17	24	35	
Table 2: Parameters of small Lucas cubes.
Dominating set
r(io)	I A(ii)
(0, 1,	0,	1,	0,	0,	0,	0,	0,	0),	(0, 1,	0,	0,	0,	1,	0,	0,	0,	0)	(1	0,	1,	0,	1,	0,	0,	0,	0,	0,	0),	(1, 0,	0,	0,	0,	1,	0,	0,	0,	0,	0)
(1, 0,	1,	0,	0,	1,	0,	0,	0,	0),	(1, 0,	0,	1,	0,	0,	1,	0,	0,	0)	(0	1,	0,	0,	0,	0,	1,	0,	0,	0,	0),	(0, 0,	0,	1,	0,	0,	1,	0,	0,	0,	0)
(0, 0,	0,	0,	1,	0,	1,	0,	0,	0),	(0, 0,	0,	0,	0,	0,	0,	1,	0,	0)	(0	0,	1,	0,	1,	0,	1,	0,	0,	0,	0),	(0, 0,	0,	0,	0,	0,	0,	1,	0,	0,	0)
(1, 0,	1,	0,	1,	0,	0,	1,	0,	0),	(1, 0,	0,	1,	0,	1,	0,	1,	0,	0)	(1	0,	1,	0,	1,	0,	0,	1,	0,	0,	0),	(0, 0,	0,	1,	0,	1,	0,	1,	0,	0,	0)
(1, 0,	0,	0,	0,	0,	0,	0,	1,	0),	(0, 0,	1,	0,	0,	0,	0,	0,	1,	0)	(1	0,	0,	1,	0,	0,	0,	0,	1,	0,	0),	(0, 0,	0,	0,	1,	0,	0,	0,	1,	0,	0)
(0, 1,	0,	0,	1,	0,	0,	0,	1,	0),	(0, 0,	0,	1,	0,	1,	0,	0,	1,	0)	(0	0,	1,	0,	0,	1,	0,	0,	1,	0,	0),	(0, 1,	0,	1,	0,	1,	0,	0,	1,	0,	0)
(0, 0,	1,	0,	0,	0,	1,	0,	1,	0),	(0, 1,	0,	1,	0,	0,	1,	0,	1,	0)	(1	0,	1,	0,	0,	0,	1,	0,	1,	0,	0),	(0, 0,	0,	0,	1,	0,	1,	0,	1,	0,	0)
(1, 0,	1,	0,	1,	0,	1,	0,	1,	0),	(0, 0,	0,	1,	0,	0,	0,	0,	0,	1)	(0	0,	1,	0,	0,	0,	0,	0,	0,	1,	0),	(0, 1,	0,	1,	0,	0,	0,	0,	0,	1,	0)
(1, 0,	0,	0,	1,	0,	0,	0,	0,	1),	(0, 0,	1,	0,	1,	0,	0,	0,	0,	1)	(0	1,	0,	0,	1,	0,	0,	0,	0,	1,	0),	(0, 0,	0,	1,	0,	1,	0,	0,	0,	1,	0)
(1, 0,	0,	0,	0,	1,	0,	0,	0,	1),	(0, 1,	0,	0,	0,	0,	1,	0,	0,	1)	(1	0,	0,	0,	0,	0,	1,	0,	0,	1,	0),	(1, 0,	0,	0,	1,	0,	1,	0,	0,	1,	0)
(1, 0,	1,	0,	0,	0,	1,	0,	0,	1),	(1, 0,	0,	0,	0,	0,	0,	1,	0,	1)	(1	0,	0,	1,	0,	0,	0,	1,	0,	1,	0),	(0, 0,	0,	0,	1,	0,	0,	1,	0,	1,	0)
(0, 1,	0,	0,	1,	0,	0,	1,	0,	1),	(0, 0,	1,	0,	0,	1,	0,	1,	0,	1)	(0	1,	0,	0,	0,	1,	0,	1,	0,	1,	0),	(1, 0,	1,	0,	0,	1,	0,	1,	0,	1,	0)
(0, 1,	0,	1,	0,	1,	0,	1,	0,	1)										(0	0,	0,	0,	0,	0,	0,	0,	0,	0,	1),	(0, 0,	1,	0,	1,	0,	0,	0,	0,	0,	1)
																		(0	1,	0,	0,	0,	1,	0,	0,	0,	0,	1),	(0, 1,	0,	0,	1,	0,	1,	0,	0,	0,	1)
																		(0	1,	0,	1,	0,	0,	0,	1,	0,	0,	1),	(0, 1,	0,	0,	1,	0,	0,	1,	0,	0,	1)
																		(0	0,	1,	0,	0,	1,	0,	1,	0,	0,	1),	(0, 1,	0,	0,	0,	0,	0,	0,	1,	0,	1)
																		(0	0,	0,	1,	0,	1,	0,	0,	1,	0,	1),	(0, 0,	1,	0,	0,	0,	1,	0,	1,	0,	1)
																		(0	1,	0,	1,	0,	0,	1,	0,	1,	0,	1)										
Table 3: Examples of minimal dominating sets for r(10) and A(11)
2-packaging set
r(ii)
I A(i2)
0, 0, 0, 0, 0 0, 0, 0, 1, 0 1, 0, 1, 0, 0
1, 0, 0, 0,	1 0, 0, 1, 0, 0
0,	1, 0, 1, 0
0,	1, 0, 0,	1
0,	1, 0, 0, 0 0, 0, 0, 1, 0
1, 0, 0, 0,	1
0, 0, 1, 0,	1 0, 0, 1, 0, 0
0,	1, 0, 1, 0 0, 0, 0, 1, 0
0, 0, 1, 0,	1
0, 0, 0 1, 0, 0 0, 1, 0 0, 0, 1 0, 1, 0 0, 0, 1 1, 0, 1 1, 0, 0 1, 0, 0 0, 0, 1 0, 0, 0 0, 1, 0 0, 0, 0 0, 1, 0
1, 0, 0
0,	1, 0
0,	1, 0
0,	1, 0 0, 0, 1 0, 0, 1 0, 0, 1 1, 0, 1 0, 0, 0 0, 0, 0 1, 0, 0 1, 0, 0
0,	1, 0
0,	1, 0
(0,	0
(0,	1
(0,	0
(0,	1
(0,	0
(0,	1
(0,	0
(0,	0
(0,	1
(0,	0
(1,	0
(0,	0
(0,	0
(0,	1
(0,	1
(0,	1
(0,	0
(0,	1
(0,	0
0, 0, 0 0, 0, 1 1, 0, 0 0, 1, 0 0, 1, 0 0, 0, 0 1, 0, 1 0, 0, 1 0, 1, 0 1, 0, 0 0, 0, 0 0, 1, 0 1, 0, 1 0, 0, 0 0, 1, 0 0, 0, 0 1, 0, 0 0, 0, 1 0, 0, 0
0, 0, 0
0,	1, 0 1, 0, 1 1, 0, 0
0,	1, 0 1, 0, 0
0,	1, 0 0, 0, 1 0, 0, 0
0,	1, 0 0, 0, 1 1, 0, 1 0, 0, 0
0,	1, 0
0,	1, 0 1, 0, 1 1, 0, 0 0, 0, 0
0,	1, 0
0, 0, 1,
0,	1, 0, 0, 0, 0,
0,	1, 0,
0,	1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0,
0,	1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0,
0,	1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1,
0,	1, 0,
0, 0, 0 0, 1, 0 0, 0, 1 1, 0, 1 0, 0, 0 1, 0, 0 0, 1, 0 0, 1, 0 0, 0, 0 1, 0, 0 0, 1, 0 0, 0, 1 0, 0, 1 0, 0, 0 0, 1, 0 0, 0, 1 1, 0, 1 0, 0, 0 0, 1, 0
0, 0
0
0
0
,0
Table 4: Examples of 2-packing sets for r(ii) and A(i2)
A. Ilic & M. Milosevic: The parameters of Fibonacci and Lucas Cubes
29
References
[1]	A. Castro, S. KlavZar, M. Mollard and Y. Rho, On the domination number and the 2-packing number of Fibonacci cubes and Lucas cubes, Comput. Math. Appl. 61 (2011), 2655-2660, doi:10.1016/j.camwa.2011.03.012, http://dx.doi.org/10.1016/j.camwa.2011. 03.012.
[2]	P. Gregor, Recursive fault-tolerance of Fibonacci cube in hypercubes, Discrete Math. 306 (2006), 1327-1341, doi:10.1016/j.disc.2004.09.017, http://dx.doi.org/10.1016/ j.disc.2004.09.017.
[3]	T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of domination in graphs, volume 208 of Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, Inc., New York, 1998.
[4]	W.-J. Hsu, Fibonacci cubes-a new interconnection topology, IEEE Transactions on Parallel and Distributed Systems 4 (1993), 3-12, doi:10.1109/71.205649.
[5]	A. Ilic, S. KlavZar and Y. Rho, Generalized Fibonacci cubes, Discrete Math. 312 (2012), 2-11, doi:10.1016/j.disc.2011.02.015, http://dx.doi.org/10.1016/j.disc.2011.02. 015.
[6]	S. KlavZar, On median nature and enumerative properties of Fibonacci-like cubes, Discrete Math. 299 (2005), 145-153, doi:10.1016/j.disc.2004.02.023, http://dx.doi.org/10. 1016/j.disc.2004.02.023.
[7]	E. Munarini, C. Perelli Cippo and N. Zagaglia Salvi, On the Lucas cubes, Fibonacci Quart. 39 (2001), 12-21.
[8]	E. Munarini and N. Z. Salvi, Structural and enumerative properties of the Fibonacci cubes, Discrete Math. 255 (2002), 317-324, doi:10.1016/S0012-365X(01)00407-1, Combinatorics '98 (Palermo), http://dx.doi.org/10.1016/S0012-365X(01)00407-1.
[9]	D. A. Pike and Y. Zou, The domination number of Fibonacci cubes, J. Combin. Math. Combin. Comput. 80 (2012), 433-444.
[10] A. Taranenko and A. Vesel, Fast recognition of Fibonacci cubes, Algorithmica 49 (2007), 81-93, doi:10.1007/s00453-007-9026-5, http://dx.doi.org/10.10 07/ s00453-007-9026-5.