A. H. Rokad

Assistant Professor in Mathematics, School of Engineering, RK.University, Rajkot - 360020, Gujarat - India

 

Corresponding author Email: rokadamit@rocketmail.com

ABSTRACT:

An injective function g:V(G)→{F0,F1,F2,...,Fn+1},where Fjis the jth Fibonacci number(j=0,1,...,n+1), is said to be Fibonacci cordial labeling if the induced functiong∗: E(G) →{0,1}defined by g ∗(xy)=(f(x)+f(y)) (mod2) satisfies the condition |eg(1)−eg(0)|≤1. A graph having Fibonacci cordial labeling is called Fibonacci cordialgraph. In this paper, i inspect the existence of Fibonacci Cordial Labeling of DS(Pn),DS(DFn),EdgeduplicationinK1, n,Jointsum ofGl(n),DFn⊕K1,nand ring sum of star graph with cycle with one chord and cycle with two chords respectively.

KEYWORDS:

Download this article as: 

Copy the following to cite this article:

Rokad A. H. Fibonacci Cordial Labeling of Some Special Graphs. Orient.J. Comp. Sci. and Technol;10(4)


Copy the following to cite this URL:

Rokad A. H. Fibonacci Cordial Labeling of Some Special Graphs. Orient. J. Comp. Sci. and Technol;10(4). Available from: http://www.computerscijournal.org/?p=7093


Introduction

The idea of Fibonacci cordial labeling was given by A. H. Rokad and G. V. Ghodasara[1]. The graphs which i considered here are Simple, undirected, connected and finite. Here V(G) and E(G) denotes the set of vertices and set of edges of a graph G respectively. For different graph theoretic symbols and nomenclature i refer Gross and Yellen[3]. A dynamic survey of labeling of graphs is released and modified every year by Gallian[4].

Definition 1

Let G = (V(G), E(G)) be a graph with V = X1∪X2∪X3∪. . . Xi∪Y

where each X i is a set of vertices having at least two vertices of the same degree

and Y=V\∪Xi.The degree splitting graph of G designated by DS (G) is acquired from G by adding vertices z1,z2, z3,. . . , zy and joining to each vertex of xi for i £[1, t].

Definition 2

The double fan DFn comprises of two fan graph that have a common path. In other words DFn = Pn+ K2

Definition3

The duplication of an edgee= xy of graph Gproduces a new graph G’by adding an edgee’= x’y ’such that N(x’)=N(x)∪{y’}−{y}and N(y’)=N(y)∪{x’}−{x}.

Definition4

The graph obtained by connecting a vertex of first copy of a graph G with a vertex of second copy of a graph G is called joint sum of two copies of G.

Definition5

A globe is a graph obtained from two isolated vertex are joined by n paths of length two.It is denoted byGl(n).

Definition 6

Ring sum G1⊕ G2of two graphs G1= (V1, E1) and G2= (V2, E2) is the graph G1⊕ G2= (V1∪ V2, (E1∪ E2) − (E1∩ E2)).

Results

Theorem 1

DS(Pn) is Fibonacci cordial.

Proof 1

Consider Pn with V (Pn) = {vi: i [1, n]}. Here V (Pn) = X1∪ X2, where X1= {xi: 2 [2, n-1]} and X2= {x1, xn}. To get DS(Pn)from G we add w1 and w2 corresponding to X1andX2.Then

|V(DS(Pn))|=n+2andE(DS(Pn))={X1w2, X2w2}∪{w1xi:i [2,n–1]}. So,|E(DS(Pn))|=−1 + 2n.

I determine labeling function g: V(G) → {F0, F1, F2, . . . , Fn+2} as below:

g(w1)= F1,

g     (w2)= Fn+1,

g(x1)= F0,

g(xi) = Fi, 2 ≤ i ≤ n.

Therefore,|eg(1)−eg(0)|≤1.

Therefore, DS(Pn) is a Fibonacci cordial graph.

Example 1

Fibonacci cordial labeling of DS(P7) can be seen in Figure 1.

Figure

Figure 1


Click here to View figure

 

Theorem 2

DS(DFn) is a Fibonacci cordial graph.

Proof2

Let G=Dfn be the double fan. Letx1, x 2,…, x nbe the path vertices of Dfn and x and y be two apex vertices. To get DS(Dfn) from G,we add w1, w2 corresponding to X1, X2,where

X1={xi: i [1, n] }and X2= {x, y}.Then|V(DS(Dfn))| = 4+ n&E(DS(Dfn)) ={xw2, y w2}∪{xiw1: i [1, n] }. So,|E(DS(Dfn))|= 1+ 4n.

I determine labeling function g:V(G)→{F0,F1,F2,…,Fn+4},as below.

For all 1 ≤ i ≤n.

g  (w1) = F3,

g(w2) = F2.

g(x) = F0,

g (y) = F1,

g(xi) = Fi+3.

Therefore |eg(1)−eg(0)|≤1.

Therefore, DS(DFn) is Fibonacci cordial.

Example 2

Fibonacci cordial labeling of DS(DF5) can be seen in Figure 2

Figure 2

Figure 2


Click here to View figure

 

Theorem 3

The graph obtained by duplication of an edge in K1, nis a Fibonacci cordial graph.

Proof3

Let x0 be the apex vertex and x 1, x 2,…, x nbe the consecutive pendant verticesofK1, n.Let G be the graph obtained by duplication of the edgee= x 0n by an e wedge e’= x0’xn’. There for einG,deg(x0) = n,deg(x0’) = n,deg(vn) = 1, deg(xn’) = 1anddeg(xi) = 2,∀ i∈{1,2,…n}. Then|V(K1, n)| =n+3 and E(K1, n) =2n.

I determine labeling function g: V(G) → {F0, F1, F2, . . . , Fn+3}, as below.

g(x0)= F1,

g (x1) = F2,

g(xn−1)=F3,

g(x0’)=F0,

g(xn’)=F4,

g(xi)=Fi+3, i [2,n],in−1.

Therefore |eg(1)−eg(0)|≤1.

Therefore,the graph obtained by duplication of an edge in K1, nis a Fibonacci cordial graph.

Example 3

A Fibonacci cordial labeling of the graph obtained by duplication of an edge e in K1, 8can be seen in the Figure 3.

Figure 3

Figure 3



Click here to View figure

 

Theorem4

The graph obtained by joint sum of two copies of Globe Gl(n)is Fibonacci cordial.

Proof4

Let G be the joint sum of two copies of Gl (n).Let{x, x’, x1, x 2,…, x n} and

{y, y ’, y1, y 2,…, y n} be the vertices of first and second copy of Gl(n)respectively.

I determine labeling function g: V(G) → {F0, F1, F2, . . . , F2n+4}, as below.

g(x) = F0,

g(x’)= F1,

g(xi)=Fi+3,i [1, n].

g(y)=F2,

g(y’)= F3,

g(yi) = Fn+i+3, i [1, n].

From the above labeling pattern i have eg   (0)=n+1andeg(1)=n.

Therefore |eg(1)−eg(0)|≤1.

Thus, the graph obtained by joint sum of two copies of Globe G l(n)is Fibonacci cordial.

Example 4

Fibonacci cordial labeling of the joint sum of two copies of Globe Gl(7) can be seen in Figure 4

Figure 4

Figure 4



Click here to View figure

 

Theorem 5

The graph DFn⊕ K1, nis a Fibonacci cordial graph for every n ∈ N .

Proof 5

Assume V(DFn⊕K1, n)= X1∪ X 2, where X1={x,w, x 1, x 2,…, x n}be the vertex set of DFn and X2={y=w, y 1, y 2,…, y n} i sthevertexsetofK1, n. Here v is the apex vertex  &   y 1, y 2,…, y n are pendant vertices of K1, n.

Also |V (DFn ⊕ K1,n)| = 2n + 2, |E(DFn ⊕ K1,n)| = 4n − 1.

I determine labeling function g:V(DFn⊕K1, n)→{F0,F1,F2,…,F2n+2},as below.

Forall1≤i≤n.

g (x)=F0,

g (w)=F1,

g(xi) = Fi+1,

g     (yi) = Fn+i+1,

From the above labeling pattern i have eg(0) = 2n and eg(1) = 2n−1.

Therefore||e g(1)−eg(0)|≤1.

Thus, the graph DFn⊕ K1, nis a Fibonacci cordial graph for every n ∈ N .

Example 5

Fibonacci cordial labeling of DF5⊕ K1, 5can be seen in Figure 5.

Figure 5

Figure 5



Click here to View figure

 

Theorem 6

The graph G ⊕ K1, nis a Fibonacci cordial graph for all n ≥4, n∈N,where G is the cycle Cn with one chord forming a triangle with two edges ofCn.

Proof 6

Let G be the cycle Cnwith one chord. Let V (G ⊕ K1, n) = X1∪ X 2, where X 1isthevertexsetofG& X 2isthevertexsetofK1, n. Let x 1, x 2,…, x nbe the successive vertices of Cn and e= x 2 xn be the chord of Cn.The vertices x1, x 2, x n forma triangle with the chorde.Here v is the a pexvertex  &   y 1, y 2,…, y nare pendant verticesofK1, n.

I determine labeling function g: V (G ⊕K1, n) → {F0, F1,F2,. . . , F2n}, as below.

CaseI:n≡0(mod3).

For all 1 ≤ i ≤ n.

g (xi) =Fi.

g(yi) = Fn+i.

CaseII:n≡1(mod3).

g (xi) = Fi, 1 ≤ i ≤ n.

g          (y1) = F0,

g(yi) = Fn+i−1, 2 ≤ i ≤ n.

From the above labeling pattern i have eg(0)=n and eg(1)=n+1.

Therefore |eg(1)−eg(0)|≤1.

Thus, the graph G ⊕ K1, nis a Fibonacci cordial graph.

Example 6

A Fibonacci cordial labeling of ring sum of C7with one chord and

K1, 7can be seen in Figure 6.

Figure 6

Figure 6



Click here to View figure

 

Theorem 7

The graph G ⊕ K1, nis a Fibonacci cordial graph for all n ≥5, n∈N,where G is the cycle with twin chords forming two triangles and another cycleCn−2with the edges of Cn.

Proof7

Let G be the cycle Cn with twin chords,where chords form two triangles and one cycle Cn−2.LetV(G⊕K1, n)=X1∪ X 2. X1={x1, x 2,…, x n} is the vertex set of Cn, e1= xn x2and e2= xn x3 are the chords of Cn. X2={y= x1, y1, y2,…, yn}is the vertex set of K1, n,where y1, y2,…, yn are pendant vertices and y= x1istheapexvertexofK1, n.Also|V(G⊕K1, n)|=2n, |E(G ⊕ K1, n)| = 2n + 2.

Take y= x 1.Also|V(G⊕K1, n)|=2n, |E(G ⊕ K1,n)| = 2n + 1.

I determine labeling function g: V(G ⊕K1, n) → {F0, F1,F2,. . . , F2n}, as below.

g      (x1)= F1,

g(x2)= F2,

g     (x3)= F3,

g       (xn) = F4,

g     (xi) = Fi+1, 4 ≤ i ≤ n − 1.

g      (yi) = Fn+i, 1 ≤ i ≤ n.

From the above labeling pattern i have eg (0)=eg(1)=n+1.

Therefore |eg(1)−eg(0)|≤1.

Thus, The graph G ⊕ K1, nis a Fibonacci cordial graph.

Example7

A Fibonacci cordial labeling of ring sum of C9 with twin chords andK1, 9can be seen in Figure7.

Figure 7

Figure 7


Click here to View figure

 

Conclusion

In this paper i investigate seven new graph which admits Fibonacci cordial labeling.

References

  1. A. H. Rokad and G. V. Ghodasara, Fibonacci Cordial Labeling of Some Special Graphs, Annals of Pure and Applied Mathematics, Vol. 11, No. 1, 2016,133−144.
  2. F.Harary,Graphtheory, Addision-wesley,Reading,MA(1969).
  3. J Gross and J Yellen, Handbook of graph theory, CRC press(2004).
  4. J. A. Gallian, A dynamic survey of graph labeling, The Electronics Journal of Combinatorics,19(2012),�DS61−260.
  5. M. Sundaram, R. Ponraj, and S. Somasundram, Prime cordial labeling of graphs,Journal of Indian Acadamy of Mathematics,27(2005),373-390.
  6. M. A. Seoud and M. A. Salim, Two upper bounds of prime cordial graphs, Journal of Combinatorial Mathematics and Combinatorial Computing,75 (2010), 95-103.
  7. S. K. Vaidya and P. L. Vihol, Prime cordial labeling for some cycle related graphs, International Journal of Open Problems in Computure Science Mathematics,3,No.5(2010),223-232.
  8. S. K. Vaidya and P.   L. Vihol,   Prime cordial labeling for some graphs, Modern Applied Science, 4, No.8 (2010), 119-126.
  9. S. K. Vaidya and N. H. Shah, Prime cordial labeling of some graphs, Open Journal of Discrete Mathematics, 2, No. 1 (2012), 11-16. doi:10.4236/ojdm.2012.21003.
  10. S. K. Vaidyaa and N. H. Shah, Prime cordial labeling of   some wheel related graphs,Malaya Journal of Matematik,4(1)(2013)148156.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 International License.

Share Knowledge: Share on LinkedInShare on FacebookTweet about this on TwitterShare on Google+Share on RedditEmail this to someone

Comments are closed.