# The Larger Bound on the Domination Number of Fibonacci Cubes and Lucas Cubes

Authors: Shengzhang Ren
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

LetΓn and Λn be the n-dimensional Fibonacci cube and Lucas cube, respectively. Denote by Γ[un,k,z] the subgraph of Γn induced by the end-vertex un,k,z that has no up-neighbor. In this paper, the number of end-vertices and domination number γ of Γn and Λn are studied. The formula of calculating the number of end-vertices is given and it is proved that γ(Γ[un,k,z])≤2k-1+1. Using these results, the larger bound on the domination number γ of Γn and Λn is determined.


---

## Body

## 1. Introduction

The Fibonacci cube and Lucas cube were presented in [1, 2], respectively. Because their many properties (see [1–7]) such as domination number, 2-packing number, and observability can be applied to interconnection networks [1].However, the number of vertices of Fibonacci cubeΓn and Lucas cube Λn grows rapidly as n increases. So it is hard to calculate exactly the number of domination number of Fibonacci cubes and Lucas cubes. The lower bound on the domination number of Fibonacci cubes and Lucas cubes is determined in [3, 6], respectively. In this paper, we will give a larger bound on the domination number of Fibonacci cubes and Lucas cubes using construction method. We begin with some basic definitions.Graphs considered in this paper are finite, simple, connected, and undirected. LetQn be the n-dimensional hypercube with n>0. A Fibonacci string b1b2⋯bn of order n is a binary string of length n without two consecutive ones. The Fibonacci cube Γn (see Figure 1) is the subgraph of Qn induced by the Fibonacci strings of length n, whose vertices are the Fibonacci strings of length n, and two vertices are joined by an edge if their Hamming distance is exactly 1. A Fibonacci string b1b2⋯bn is a Lucas string if b1bn=0. The Lucas cube Λn is the subgraph of Qn induced by the Lucas strings of length n. It is well known that |V(Γn)|=Fn+2 and |V(Λn)|=Ln, where Fn and Ln are Fibonacci numbers and Lucas numbers, respectively. Recall that the Fibonacci numbers and Lucas numbers form a sequence of positive integers Fn and Ln, respectively, where F1=1,F2=1, and Fn=Fn-1+Fn-2 and L1=1,L2=3, and Ln=Ln-1+Ln-2 for n>2.Figure 1
Γ
1
,
Γ
2
,
Γ
3, and Γ4.For a connected graphG, the distance dG(u,v) between vertices u and v is the usual shortest path distance. For 0≤k≤n, n≥1, let Γn,k be the set of vertices of Γn that contain k ones. Hence Γn,k is the set of vertices of Γn at distance k from b1b2⋯bn,bi=0,1≤i≤n. Λn,k is defined analogously. If uv∈Γn, where u∈Γn,k and v∈Γn,k-1 for k≥1, then we call v a down-neighbor of u and u an up-neighbor of v.If a vertexu has no up-neighbor, we call it an end-vertex and denote by σ(Γn) the number of end-vertices of Γn. Let un,k,z(0≤k≤n/2,z≥0,n≥1) be an end-vertex with string length n, where k,z are the number of ones and consecutive 02, respectively. We denote by Γ[un,k,z] the subgraph of Γn induced by the end-vertex un,k,z, whose strings of vertices were obtained from string of the vertex un,k,z by changing i ones into i zeroes (i=0,1,2,…,k) and any two vertices have an edge if their Hamming distance is exactly 1 (see Figure 2).Figure 2
Γ
[
u
n
,
k
,
z
], un,k,z=101001.LetG be a graph. Then D⊆V(G) is a dominating set if every vertex from V(G)∖D is adjacent to some vertex from D. The domination number γ(G) is the minimum cardinality of a dominating set of G.All graph-theoretical terms and concepts used but unexplained in this paper are standard, and that can be found in many textbooks such as [8].


## 2. The Larger Bound on the Domination Number of Fibonacci Cubes

In this section, we will determine the larger bound on the domination number of Fibonacci cubes. Firstly, we mention the following properties of Fibonacci cubes which will be used later.Lemma 1 (see [3]).
Letn≥3 and k≥2. Then any different u,v∈Γn,k have different sets of down-neighbors.Lemma 2 (see [6]).
For anyn≥4, γ(Γn)≥⌈(Fn-3)/(n-2)⌉.Lemma 3.
Letun,k,z be an end-vertex with string length n, where k and z are the number of ones and consecutive 02, respectively. Then γ(Γ[un,k,z])≤2k-1+1 (see Figure 2).Proof.
LetCnm=(n·(n-1)⋯(n-m+1))/(m·(m-1)⋯2·1), and it will be frequently used in latter. Let u=un,k,z, and vhj be a vertex with dΓ[un,k,z](u,vhj)=j(1≤h≤Ckj,j=1,2,…,k), and
(1)Φ={u,v11,v21,…,v⌊Ck1/2⌋1,v12,v22,…,v⌊Ck2/2⌋2,…,v1k-1,v2k-1,…,v⌊Ckk-1/2⌋k-1,v1k},
whose subset {v1i,v2i,…,v⌊Cki/2⌋i}(i=2,3,…,k-1) contains all vertices {vhi∣1≤h≤Cki} such that satisfy the condition dΓ[un,k,z](vli-1,vhi)≠1 for l=1,2,…,⌊Cki-1/2⌋. We will prove that Φ is a dominating set. In order to prove that Φ is a dominating set. It suffices to prove that any ⌊Cki-1/2⌋ vertices in {v1i-1,v2i-1,…,vCki-1i-1} can dominate ⌊Cki/2⌋ vertices in {v1i,v2i,…,vCkii}. If Cki-1≥Cki, the result is obviously correct. We assume that Cki-1<Cki. From Lemma 1, we know that any different vhi-1,vli-1∈V(Γ[un,k,z])(1≤h,l≤Cki-1,h≠l) have different sets of down-neighbors and have at most one common down-neighbor vertex. Since each vertex vhi-1 has exactly k-i+1 ones. If k-i+2≥⌊Cki-1/2⌋, then the number of vertices dominated by vertices set {v1i-1,v2i-1,…,v⌊Cki-1/2⌋i-1} is at least as follows:
(2)∑j=1⌊Cki-1/2⌋‍(k-i-j+2)=⌊Cki-1(2k-2i+3-⌊Cki-1/2⌋)4⌋≥⌊Cki-1(k-i+1)4⌋=⌊iCki4⌋≥⌊Cki2⌋(Sincei≥2).
Ifk-i+2<⌊Cki-1/2⌋, there must exist integer m such that m<⌊Cki-1/2⌋ and k-i-m+1=0, and then the number of vertices dominated by vertices set {v1i-1,v2i-1,…,v⌊Cki-1/2⌋i-1} is at least as follows:
(3)∑j=1m‍(k-i-j+2)=Cki>⌊Cki2⌋.
Therefore the set Φ is a dominating set, and
(4)|Φ|=2+∑i=1k-1⌊Cki2⌋≤2k-1+1.
This completes our proof.Theorem 4.
Letσ(Γn) be the number of end-vertices in Γn. Then the followings hold.(i)
Ifn(n=2p+1) is odd, then
(5)σ(Γ2p+1)={1+∑k=1(p-1)/3‍(Cp-k2k-1+Cp-k2k)+∑k=1(p+2)/3‍(Cp-k2k-2+Cp-k2k-1)ifn≡0mod⁡3;1+∑k=1p/3‍(Cp-k2k-1+Cp-k2k)+∑k=1p/3‍(Cp-k2k-2+Cp-k2k-1)ifn≡1mod⁡3;1+∑k=1(p+1)/3‍(Cp-k2k-1+Cp-k2k)+∑k=1(p+1)/3‍(Cp-k2k-2+Cp-k2k-1)ifn≡2mod⁡3.(ii)
Ifn(n=2p) is even, then
(6)σ(Γ2p)={1+∑k=1p/3‍(Cp-k2k-2+Cp-k2k-1)+∑k=2(p+3)/3‍(Cp-k2k-3+Cp-k2k-2)ifn≡0mod⁡3;1+∑k=1(p+1)/3‍(Cp-k2k-2+Cp-k2k-1)+∑k=2(p+1)/3‍(Cp-k2k-3+Cp-k2k-2)ifn≡1mod⁡3;1+∑k=1(p+2)/3‍(Cp-k2k-2+Cp-k2k-1)+∑k=2(p+2)/3‍(Cp-k2k-3+Cp-k2k-2)ifn≡2mod⁡3.Proof.
We prove only that the theorem is correct ifn(n=2p+1) is odd and n≡0mod⁡3. And the proofs of the others cases are similar. End-vertices of Γn can be divided into two cases as follows.
Case  1. The end-vertices set is composed of end-vertices with strings form 1b2b3⋯bn.
Case  2. The end-vertices set is composed of end-vertices with strings form 0b2b3⋯bn.
In Case 1, sincen=2p+1 and n≡0mod⁡3, then end-vertices {un,k,z} are divided into ((4p-1)/3)+1 cases with z=0,1,2,…,(4p-1)/3. Therefore the number of end-vertices with strings form 1b2b3⋯bn is
(7)1+∑k=1(p-1)/3‍(Cp-k2k-1+Cp-k2k).
In Case 2, as similar as Case 1, end-vertices{un,k,z} are divided into ((4p+2)/3)+1 cases with z=0,1,2,…,(4p+2)/3. Then the number of end-vertices with strings form 0b2b3⋯bn is
(8)∑k=1(p+2)/3‍(Cp-k2k-2+Cp-k2k-1).
Therefore
(9)σ(Γ2p+1)=1+∑k=1(p-1)/3‍(Cp-k2k-1+Cp-k2k)+∑k=1(p+2)/3‍(Cp-k2k-2+Cp-k2k-1)n≡0mod⁡3.
This completes our proof.Now we give the larger bound on the domination number of Fibonacci cubes as follows.Theorem 5.
Letn>4. Then for the Fibonacci cube Γn the followings hold.(i)
Ifn(n=2p+1) is odd, then
(10)⌈Fn-3n-2⌉≤γ(Γn)≤{2p+2+∑k=1(p-1)/3‍(Cp-k2k-1+Cp-k2k)(2p-k-1)+∑k=1(p+2)/3‍(Cp-k2k-2+Cp-k2k-1)(2p-k-1)ifn≡0mod⁡3;2p+2+∑k=1p/3‍(Cp-k2k-1+Cp-k2k)(2p-k-1)+∑k=1p/3‍(Cp-k2k-2+Cp-k2k-1)(2p-k-1)ifn≡1mod⁡3;2p+2+∑k=1(p+1)/3‍(Cp-k2k-1+Cp-k2k)(2p-k-1)+∑k=1(p+1)/3‍(Cp-k2k-2+Cp-k2k-1)(2p-k-1)ifn≡2mod⁡3.(ii)
Ifn(n=2p) is even, then
(11)⌈Fn-3n-2⌉≤γ(Γn)≤{2p-1+2+∑k=1p/3‍(Cp-k2k-2+Cp-k2k-1)(2p-k-1)+∑k=2(p+3)/3‍(Cp-k2k-3+Cp-k2k-2)(2p-k-1)ifn≡0mod⁡3;2p-1+2+∑k=1(p+1)/3‍(Cp-k2k-2+Cp-k2k-1)(2p-k-1)+∑k=2(p+1)/3‍(Cp-k2k-3+Cp-k2k-2)(2p-k-1)ifn≡1mod⁡3;2p-1+2+∑k=1(p+2)/3‍(Cp-k2k-2+Cp-k2k-1)(2p-k-1)+∑k=2(p+2)/3‍(Cp-k2k-3+Cp-k2k-2)(2p-k-1)ifn≡2mod⁡3.Proof.
According to the process of proof of Lemma3, there must exist a dominating set of Γ[un,k,z] with the string form 1b2⋯bn (or 0b2⋯bn) such that it contains the vertex with the string form 10n-1 (or 010n-2). So all dominating sets of Γ[un,k,z] of Γn with strings form 1b2⋯bn (or 0b2⋯bn) have at least two common vertices with strings {10n-1,0n} (or {010n-2,0n}). Then the theorem follows directly from Lemmas 2 and 3 and Theorem 4.


## 3. The Larger Bound on the Domination Number of Lucas Cubes

In this section, we will determine the larger bound on the domination number of Lucas cubes as follows.Lemma 6 (see [3]).
For anyn≥7, γ(Λn)≥⌈(Ln-2n)/(n-3)⌉.Theorem 7.
Letσ(Λn) be the number of end-vertices in Λn. Then the followings hold.(i)
Ifn(n=2p+1) is odd, then
(12)σ(Λ2p+1)={∑k=1(p-1)/3‍Cp-k2k-1+∑k=1(p+2)/3‍(Cp-k2k-2+Cp-k2k-1)ifn≡0mod⁡3;∑k=1p/3‍Cp-k2k-1+∑k=1p/3‍(Cp-k2k-2+Cp-k2k-1)ifn≡1mod⁡3;∑k=1(p+1)/3‍Cp-k2k-1+∑k=1(p+1)/3‍(Cp-k2k-2+Cp-k2k-1)ifn≡2mod⁡3.(ii)
Ifn(n=2p) is even, then
(13)σ(Λ2p)={1+∑k=1p/3‍Cp-k2k-2+∑k=2(p+3)/3‍(Cp-k2k-3+Cp-k2k-2)ifn≡0mod⁡3;1+∑k=1(p+1)/3‍Cp-k2k-2+∑k=2(p+1)/3‍(Cp-k2k-3+Cp-k2k-2)ifn≡1mod⁡3;1+∑k=1(p+2)/3‍Cp-k2k-2+∑k=2(p+2)/3‍(Cp-k2k-3+Cp-k2k-2)ifn≡2mod⁡3.Proof.
The proof is similar to Theorem4.Theorem 8.
Letn>7. Then for the Lucas cube Λn the followings hold.(i)
Ifn(n=2p+1) is odd, then
(14)⌈Ln-2nn-3⌉≤γ(Λn)≤{2+∑k=1(p-1)/3‍Cp-k2k-1(2p-k-1)+∑k=1(p+2)/3‍(Cp-k2k-2+Cp-k2k-1)(2p-k-1)ifn≡0mod⁡3;2+∑k=1p/3‍Cp-k2k-1(2p-k-1)+∑k=1p/3‍(Cp-k2k-2+Cp-k2k-1)(2p-k-1)ifn≡1mod⁡3;2+∑k=1(p+1)/3‍Cp-k2k-1(2p-k-1)+∑k=1(p+1)/3‍(Cp-k2k-2+Cp-k2k-1)(2p-k-1)ifn≡2mod⁡3.(ii)
Ifn(n=2p) is even, then
(15)⌈Ln-2nn-3⌉≤γ(Λn)≤{2p-1+2+∑k=1p/3‍Cp-k2k-2(2p-k-1)+∑k=2(p+3)/3‍(Cp-k2k-3+Cp-k2k-2)(2p-k-1)ifn≡0mod⁡3;2p-1+2+∑k=1(p+1)/3‍Cp-k2k-2(2p-k-1)+∑k=2(p+1)/3‍(Cp-k2k-3+Cp-k2k-2)(2p-k-1)ifn≡1mod⁡3;2p-1+2+∑k=1(p+2)/3‍Cp-k2k-2(2p-k-1)+∑k=2(p+2)/3‍(Cp-k2k-3+Cp-k2k-2)(2p-k-1)ifn≡2mod⁡3.Proof.
That follows directly from Lemmas6 and Theorem 7.



---

*Source: 954738-2014-03-04.xml*