10.1Introduction

We begin with simple, finite, undirected graph G, where V(G) and E(G) are the vertex set and edge set of G respectively. For all other terminology we follow Gross [4]. Now we provide a brief summary of definitions and other information which are necessary for the present investigations.

10.1.1Definition

Definition. The Fibonacci sequence can be defined by the linear recurrence relation satisfying:

Definition. Let f: V(G) → {0, 1} for each edge uv assigned the label |f(u) − f(v)|, then f is said to be a cordial labeling [2] of G if the number of vertices with label 0 and the number of vertices with label 1 differ at most by 1, and the number of edges with label 0 and the number of edges with label 1 differ by at most 1.

Definition. An injective function f: V(G) → {F₀, F₁, F₂, …, F_n}, where F_j is the j^th Fibonacci number, is said to be Fibonacci cordial labeling [5] if the induced function f*: E(G) → {0, 1} defined by f*(uv) = (f(u) + f(v))(mod 2) satisfies the condition |e_f(0) − e_f(1)| ≤ 1, where e_f(0) and e_f(1) are the total number of edges with label 0 and 1 respectively. A graph which admits Fibonacci cordial labeling is called a Fibonacci cordial graph. It was first introduced by Rokad and Ghodasara in [6].

Karthikeyan et. al. showed that the wheel graph and bistar graph are Fibonacci cordial graphs [5].

We also note that F_n is even if and only if n ≡ 0 (mod 3).

Definition. The graph W_n = C_n + K₁ is called a wheel graph [3]. The vertex corresponding to K₁ is called the apex vertex and the vertices corresponding to C_n are called rim vertices.

Definition. The circulant graph [7] C_n(a₁, a₂, …, a_m) is the graph with vertex set {v₁, v₂, …, v_m} and the edge set {vivi+aj,1≤i≤n,1≤j≤m} where addition of indices in modulo n and m, n, a₁, a₂, …, a_m are positive integers such that 1≤ai≤⌊n2⌋ and the a_i’s are distinct. Cnk is the generalization of the circulant graphs C_n(1, 2, 3, …, k) given by Anholcer and Palmer [1].

In this chapter, we use the notation Cn2 for the circulant graph C_n(1, 2). Cn2 can also be considered as square of cycle graph C_n.

Definition. A helm graph [3] is obtained from the wheel graph W_n by adding a pendent edge on each rim vertex of the wheel.

Definition. The friendship graph [3] is one point union of C₃ which is denoted by Fn=C3n, where n stands for the total number of C₃.

10.2Main Results

Theorem 10.1

C_n is a Fibonacci cordial graph if and only if n ≡ 0, 1, 3 (mod 4) and n ≥ 3.◼

Proof.Case 1: n ≡ 0, 1, 3 (mod 4).

We label all the consecutive vertices of cycle C_n as v₁, v₂, v₃, …, v_n. Thus, |V(C_n)| = |E(C_n)| = n.

Sub case 1: n ≡ 1 (mod 6).

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_n} such that, f(v₁) = F₀, f(v₂) = F₁, f(v₃) = F₂, f(v₄) = F₄, f(v₅) = F₃, f(v₆) = F₆ and f(v₇) = F₅ and for n > 7:

Then ef(1)=n+12 and ef(0)=n−12.

Sub case 2: n ≡ 8 (mod 12).

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_n} such that, f(v₁) = F₀, f(v₂) = F₁ and for n > 2:

Then ef(1)=n2 and ef(0)=n2.

Sub case 3: n ≡ 3 (mod 6).

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_n} such that, f(v₁) = F₀, f(v₂) = F₁, f(v₃) = F₂ and for n > 3:

Then ef(0)=n−12 and ef(1)=n+12, for n = 3 and ef(1)=n−12 and ef(0)=n+12, for n > 3.

Sub case 4: n ≡ 4 (mod 12).

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_n} such that, f(v₁) = F₀, f(v₂) = F₃, f(v₃) = F₁, f(v₄) = F₂ and for n > 4:

Then ef(0)=n2 and ef(1)=n2.

Sub case 5: n ≡ 5 (mod 6).

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_n} such that, f(v₁) = F₀, f(v₂) = F₃, f(v₃) = F₁, f(v₄) = F₂, f(v₅) = F₄ and for n > 5:

Then ef(0)=n+12 and ef(1)=n−12, for n = 5 and ef(0)=n−12 and ef(1)=n+12, for n > 5.

Sub case 6: n ≡ 0 (mod 12).

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_n} such that,

Then ef(1)=n2 and ef(0)=n2.

Thus, for all the above cases, |e_f(0) − e_f(1)| ≤ 1. Hence, C_n admits Fibonacci cordial labeling for n ≡ 0, 1, 3 (mod 4) and n ≥ 3.

Case 2: n ≡ 2 (mod 4). Hence, n = 4k + 2 for some positive integer k. Thus, |V(C_n)| = |E(C_n)| = 2(2k + 1). Clearly, to satisfy the condition of Fibonacci cordial labeling e_f(0) = e_f(1) = 2k + 1, which is an odd number. Suppose, we label the consecutive vertices of C_n with even Fibonacci numbers {F_3i, 0 ≤ 3i ≤ n} and the remaining vertices with odd Fibonacci numbers. In this case, e_f(0) = 4k and e_f(1) = 2. Now, if we interchange the labels of two vertices having odd and even Fibonacci numbers respectively then e_f(0) = 4k − 2 and e_f(1) = 4. Continuing in such a manner we obtain e_f(0) = 2k + 2 and e_f(1) = 2k. So e_f(0) and e_f(1) will always be even. Hence, |e_f(0) − e_f(1)| ≥ 2. So C_n is not a Fibonacci cordial graph for n ≡ 2 (mod 4).

□

Theorem 10.2

Cn2 is a Fibonacci cordial graph if n is even and n ≥ 4.◼

Proof. Let G=Cn2, we label all the consecutive vertices of the cycle C_n as v₁, v₂, v₃, …, v_n. Thus, |V(G)| = n and |E(G)| = 2n.

Case 1: n ≡ 0 (mod 6).

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_n} such that,

Thus, e_f(1) = e_f(0) = n.

Case 2: n ≡ 2 (mod 6).

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_n} such that, f(v₁) = F₀, f(v₂) = F₁, f(v₃) = F₃ and for n > 3:

Thus, e_f(1) = e_f(0) = n.

Case 3: n ≡ 4 (mod 6).

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_n} such that, f(v₁) = F₀, f(v₂) = F₁, f(v₃) = F₃ and for n > 3:

Thus e_f(1) = e_f(0) = n.

Thus, from all the above cases, |e_f(0) − e_f(1)| ≤ 1. Hence, Cn2 admits Fibonacci cordial labeling.□

Theorem 10.3

Comb graph Pn⊙K1 is a Fibonacci cordial graph.◼

Proof. We label all the consecutive vertices of the path P_n in G=Pn⊙K1 as v₁, v₂, v₃, …, v_n, v_n+1. We label all the vertices as {u_i, 1 ≤ i ≤ n + 1} corresponding to each of the vertices {v_i, 1 ≤ i ≤ n + 1}. Clearly, |V(G)| = 2n + 2 and |E(G)| = 2n + 1.

In all the below cases let S be a set of unlabeled vertices and g be an injective function form S to F_3i+1, F_3i+2, 0 ≤ 3i + 1, 3i + 2 ≤ 2n + 2.

Case 1: 1 ≤ n ≤ 6.

Sub case 1: n is odd.

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+2} such that,

Sub case 2: n = 2.

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+2} such that,

Sub case 3: n = 4, 6.

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+2} such that,

Case 2: n > 6.

Sub case 1: n ≡ 1 (mod 6).

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+2} such that,

Sub case 2: n ≡ 2 (mod 6).

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+2} such that,

Sub case 3: n ≡ 3, 5 (mod 6).

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+2} such that,

Sub case 4: n ≡ 0, 4 (mod 6).

We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+2} such that,

Thus, for all the above cases |e_f(0) − e_f(1)| ≤ 1. Hence, the comb graph is Fibonacci cordial graph.□

Theorem 10.4

A helm graph is a Fibonacci cordial graph.◼

Proof. We label the apex vertex as v₀ and all the consecutive vertices of the cycle C_n in H_n as v₁, v₂, v₃, …, v_n. We label all the vertices as {w_i, 1 ≤ i ≤ n} corresponding to each of the vertices {v_i, 1 ≤ i ≤ n}. Clearly, |V(H_n)| = 2n + 1 and |E(H_n)| = 3n.

Case 1: n ≡ 1 (mod 6).

Let g be any injection from the set S={v1,v2,…,vn−32}⋃{vn+12,vn+32,…,vn} ⋃{wn+12,wn+32,…,wn} to the set {F3i+1,F3i+2,i=0,1,2,…,[2n+13]}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+1} such that,

Then ef(0)=⌈3n2⌉ and ef(1)=⌊3n2⌋.

Case 2: n ≡ 3, 5 (mod 6).

Let g be any bijection from the set S={v1,v2,…,vn−32}⋃{vn+12,vn+32,…,vn}⋃{wn+12,wn+32,…,wn} to the set {F3i+1,F3i+2,i=0,1,2,…,2n+13}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+1} such that,

Then ef(0)=⌈3n2⌉ and ef(1)=⌊3n2⌋.

Case 3: n ≡ 0, 2, 4 (mod 6).

Sub case 1: n = 4.

Let g be an injection from the set S={v1,v3,v4}⋃{w2,w3,w4} to the set {F₁, F₂, F₄, F₅, F₇, F₈, F₉}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F₈} such that,

Then e_f(1) = e_f(0) = 6.

Sub case 2: n ≥ 6.

Let g be an injection from the set S={vn2+⌊n6⌋,vn2+⌊n6⌋+1,…,vn} ⋃ {v1,v2,…,vn2−1} ⋃ {wn2+1,wn2+2,…,wn} to the set {F3i+1,F3i+2,i=0,1,2,…,[2n+13]}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+1} such that,

Then ef(1)=ef(0)=3n2.

Thus, from all the above cases |e_f(0) − e_f(1)| ≤ 1. Hence, H_n admits Fibonacci cordial labeling. H_n is a Fibonacci cordial graph.□

Theorem 10.16

A friendship graph is a Fibonacci cordial graph.◼

Proof. A friendship graph is one point union of C₃ which is denoted by Fn=C3n, where n stands for the total number of C₃. We label the center vertex as v₀. All other vertices are labeled with {v_i, i = 1, 2, 3, …, 2n} consecutively. Thus, |V(F_n)| = 2n + 1 and |E(F_n)| = 3n.

Case 1: n ≡ 1 (mod 6).

Sub case 1: n = 1.

We define an injective function f: V(G) → {F₀, F₁, F₂} such that, f(v₀) = F₀, f(v₁) = F₁, f(v₂) = F₂. Thus, e_f(0) = 1 and e_f(1) = 2.

Sub case 2: n ≡ 1 (mod 12) and n > 1.

Let g be a injection from the set S={vi,i=n+32+2k,k=0,1,2,…,3(n−1)4} ⋃ {vi,i=5n+16+2k,k=0,1,2,…,7(n−1)12} to the set

{F3i+1,F3i+2,i=0,1,2,…,[2n+13]}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+1} such that,

By the above induced labeling we obtain, ef(0)=⌊3n2⌋ and ef(1)=⌈3n2⌉.

Sub case 3: n = 7.

Let g be an injection from the set S = {v_i, i = 5, 6, …, 14} to the set {F_3i+1, F_3i+2, i = 0, 1, 2, 3, 4}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+1} such that,

By the above induced labeling we obtain, e_f(1) = 10 and e_f(0) = 11.

Sub case 4: n ≡ 7 (mod 12) and n > 7.

Let g be an injection from the set S={vi,i=n−72+2k,k=0,1,2,…,3n−54} ⋃ {vi,i=5(n−1)6+2k,k=0,1,2,…,7n−112} to the set {F3i+1,F3i+2,i=0,1,2,…,[2n+13]}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_n−1} such that,

By the above induced labeling we obtain, ef(1)=⌊3n2⌋ and ef(0)=⌈3n2⌉.

Case 2: n ≡ 0 (mod 12).

Let g be an injection from the set S={vi,i=n+42+2k,k=0,1,2,…,3n−44} ⋃ {vi,i=5n+66+2k,k=0,1,2,…,7n−1212} to the set {F3i+1,F3i+2,i=0,1,2,…,[2n+13]}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+1} such that,

By the above induced labeling we obtain, ef(1)=ef(0)=3n2.

Case 3: n ≡ 8 (mod 12).

Let g be an injection from the set S={vi,i=n+42+2k,k=0,1,2,…,3n−44} ⋃ {vi,i=5n+26+2k,k=0,1,2,…,7n−812} to the set {F3i+1,F3i+2,i=0,1,2,…,[2n+13]}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+1} such that,

By the above induced labeling we obtain, ef(1)=ef(0)=3n2.

Case 4: n ≡ 3( mod 6).

Sub case 1: n = 3.

Let g be an injection from the set S = {v_i, i = 3, 4, 5, 6} to the set {F_3i+1, F_3i+2, i = 0, 1}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+1} such that,

By the above induced labeling we obtain, e_f(1) = 4 and e_f(0) = 5.

Sub case 2: n ≡ 3 (mod 12) and n > 3.

Let g be an injection from the set S={vi,i=n+52+2k,k=0,1,2,…,3n−54} ⋃ {vi,i=5n+36+2k,k=0,1,2,…,7n−912} to the set {F3i+1,F3i+2,i=0,1,2,…,[2n+13]}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_n−1} such that,

By the above induced labeling we obtain, ef(1)=⌊3n2⌋ and ef(0)=⌈3n2⌉.

Sub case 3: n ≡ 9 (mod 12).

Let g be an injection from the set S={vi,i=5n−96+2k,k=0,1,2,…,7n+912} ⋃ {vi,i=5n+96+2k,k=0,1,2,…,7n−1512} to the set {F3i+1,F3i+2,i=0,1,2,…,[2n+13]}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+1} such that,

By the above induced labeling we obtain, ef(0)=⌊3n2⌋ and ef(1)=⌈3n2⌉.

Case 5: n ≡ 4 (mod 6).

Sub case 1: n = 4.

Let g be an injection from the set S = {v_i, i = 3, 4, …, 8} to the set

{F_3i+1, F_3i+2, i = 0, 1, 2}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+1} such that,

By the above induced labeling we obtain, e_f(1) = e_f(0) = 6. Thus, |e_f(0) − e_f(1)| ≤ 1.

Sub case 2: n > 4.

Let g be an injection from the set S={vi,i=n+42+2k,k=0,1,2,…,3n−44} ⋃ {vi,i=5n−26+2k,k=0,1,2,…,n−106} to the set

{F3i+1,F3i+2,i=0,1,2,…,[2n+13]}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+1} such that,

By the above induced labeling we obtain, ef(1)=ef(0)=3n2.

Case 6: n ≡ 5 (mod 6).

Sub case 1: n = 5.

Let g be an injection from the set S={vi,i=4,5,…,10} to the set

{F3i+1,i=0,1,2,3}⋃{F3i+2,i=0,1,2}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+1} such that,

By the above induced labeling we obtain, e_f(1) = 8 and e_f(0) = 7.

Sub case 2: n ≡ 5 (mod 12) and n > 5.

Let g be an injection from the set S={vi,i=n+32+2k,k=0,1,2,…,3n−34} ⋃{vi,i=5n+56+2k,k=0,1,2,…,7n−1112} to the set

{F3i+1,F3i+2,i=0,1,2,…,[2n+13]}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+1} such that,

By the above induced labeling we obtain, ef(0)=⌊3n2⌋ and ef(1)=⌈3n2⌉.

Sub case 3: n ≡ 11 (mod 12).

Let g be an injection from the set S={vi,i=n+52+2k,k=0,1,2,…,3n−54} ⋃{vi,i=5n−16+2k,k=0,1,2,…,7n−512} to the set {F3i+1,F3i+2,i=0,1,2,…,[2n+13]}. We define an injective function f: V(G) → {F₀, F₁, F₂, …, F_2n+1} such that,