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)→{F_{0},F_{1},F_{2},...,F_{n+1}},where F_{j}is 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 |e_{g}(1)−e_{g}(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),EdgeduplicationinK_{1, n},Jointsum ofGl(n),DFn⊕K_{1,n}and 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 = X_{1}∪X_{2}∪X_{3}∪. . . 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 z_{1},z_{2}, z_{3},. . . , z_{y }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+ K_{2 }
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 G_{1}⊕ G_{2}of two graphs G_{1}= (V_{1}, E_{1}) and G_{2}= (V_{2}, E_{2}) is the graph G_{1}⊕ G_{2}= (V_{1}∪ V_{2}, (E_{1}∪ E_{2}) − (E_{1}∩ E_{2})).
Results
Theorem 1
DS(Pn) is Fibonacci cordial.
Proof 1
Consider Pn with V (Pn) = {v_{i}: i [1, n]}. Here V (Pn) = X_{1}∪ X_{2}, where X_{1}= {x_{i}: 2 [2, n-1]} and X_{2}= {x_{1}, x_{n}}. To get DS(Pn)from G we add w_{1 }and w_{2 }corresponding to X_{1}andX_{2}.Then
|V(DS(Pn))|=n+2andE(DS(Pn))={X_{1}w_{2}, X_{2}w_{2}}∪{w_{1}x_{i}:i [2,n–1]}. So,|E(DS(Pn))|=−1 + 2n.
I determine labeling function g: V(G) → {F_{0}, F_{1}, F_{2}, . . . , F_{n+2}} as below:
g(w_{1})= F_{1},
g (w_{2})= F_{n+1},
g(x_{1})= F_{0},
g(x_{i}) = F_{i}, 2 ≤ i ≤ n.
Therefore,|e_{g}(1)−e_{g}(0)|≤1.
Therefore, DS(Pn) is a Fibonacci cordial graph.
Example 1
Fibonacci cordial labeling of DS(P_{7}) can be seen in Figure 1.
Figure 1 |
Theorem 2
DS(DFn) is a Fibonacci cordial graph.
Proof2
Let G=Dfn be the double fan. Letx_{1}, x _{2},…, x _{n}be the path vertices of Dfn and x and y be two apex vertices. To get DS(Dfn) from G,we add w_{1}, w_{2 }corresponding to X_{1}, X_{2},where
X_{1}={x_{i}: i [1, n] }and X_{2}= {x, y}.Then|V(DS(Dfn))| = 4+ n&E(DS(Dfn)) ={xw_{2}, y w_{2}}∪{x_{i}w_{1}: i [1, n] }. So,|E(DS(Dfn))|= 1+ 4n.
I determine labeling function g:V(G)→{F_{0},F_{1},F_{2},…,F_{n+4}},as below.
For all 1 ≤ i ≤n.
g (w_{1}) = F_{3},
g(w_{2}) = F_{2}.
g(x) = F_{0},
g (y) = F_{1},
g(x_{i}) = F_{i+3}.
Therefore |e_{g}(1)−e_{g}(0)|≤1.
Therefore, DS(DFn) is Fibonacci cordial.
Example 2
Fibonacci cordial labeling of DS(DF_{5}) can be seen in Figure 2
Figure 2 |
Theorem 3
The graph obtained by duplication of an edge in K_{1, n}is a Fibonacci cordial graph.
Proof3
Let x_{0 }be the apex vertex and x _{1}, x _{2},…, x _{n}be the consecutive pendant verticesofK_{1, n}.Let G be the graph obtained by duplication of the edgee= x _{0} x _{n }by an e wedge e’= x_{0}’x_{n}’. There for einG,deg(x_{0}) = n,deg(x_{0}’) = n,deg(v_{n}) = 1, deg(x_{n}’) = 1anddeg(x_{i}) = 2,∀ i∈{1,2,…n}. Then|V(K_{1, n})| =n+3 and E(K_{1, n}) =2n.
I determine labeling function g: V(G) → {F_{0}, F_{1}, F_{2}, . . . , F_{n+3}}, as below.
g(x_{0})= F_{1},
g (x_{1}) = F_{2},
g(x_{n−1})=F_{3},
g(x_{0}’)=F_{0},
g(x_{n}’)=F_{4},
g(x_{i})=F_{i}_{+3}, i [2,n],in−1.
Therefore |e_{g}(1)−e_{g}(0)|≤1.
Therefore,the graph obtained by duplication of an edge in K_{1, n}is a Fibonacci cordial graph.
Example 3
A Fibonacci cordial labeling of the graph obtained by duplication of an edge e in K_{1, 8}can be seen in the Figure 3.
Figure 3 |
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’, x_{1}, x _{2},…, x _{n}} and
{y, y ’, y_{1}, y _{2},…, y _{n}} be the vertices of first and second copy of Gl(n)respectively.
I determine labeling function g: V(G) → {F_{0}, F_{1}, F_{2}, . . . , F_{2n+4}}, as below.
g(x) = F_{0},
g(x’)= F_{1},
g(x_{i})=F_{i+3},i [1, n].
g(y)=F_{2},
g(y’)= F_{3},
g(y_{i}) = F_{n+i+3}, i [1, n].
From the above labeling pattern i have eg (0)=n+1ande_{g}(1)=n.
Therefore |e_{g}(1)−e_{g}(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 |
Theorem 5
The graph DF_{n}⊕ K_{1, n}is a Fibonacci cordial graph for every n ∈ N .
Proof 5
Assume V(DF_{n}⊕K_{1, n})= X_{1}∪ X _{2}, where X_{1}={x,w, x _{1}, x _{2},…, x _{n}}be the vertex set of DF_{n }and X_{2}={y=w, y _{1}, y _{2},…, y _{n}} i sthevertexsetofK_{1, n}. Here v is the apex vertex & y _{1}, y _{2},…, y _{n }are pendant vertices of K_{1, n}.
Also |V (DFn ⊕ K_{1,n})| = 2n + 2, |E(DFn ⊕ K_{1,n})| = 4n − 1.
I determine labeling function g:V(DF_{n}⊕K_{1, n})→{F_{0},F_{1},F_{2},…,F_{2n+2}},as below.
Forall1≤i≤n.
g (x)=F_{0},
g (w)=F_{1},
g(x_{i}) = F_{i+1},
g (y_{i}) = F_{n+i+1},
From the above labeling pattern i have e_{g}(0) = 2n and e_{g}(1) = 2n−1.
Therefore||e _{g}(1)−e_{g}(0)|≤1.
Thus, the graph DF_{n}⊕ K_{1, n}is a Fibonacci cordial graph for every n ∈ N .
Example 5
Fibonacci cordial labeling of DF_{5}⊕ K_{1, 5}can be seen in Figure 5.
Figure 5 |
Theorem 6
The graph G ⊕ K_{1, n}is a Fibonacci cordial graph for all n ≥4, n∈N,where G is the cycle C_{n }with one chord forming a triangle with two edges ofC_{n}.
Proof 6
Let G be the cycle C_{n}with one chord. Let V (G ⊕ K_{1, n}) = X_{1}∪ X _{2}, where X _{1}isthevertexsetofG& X _{2}isthevertexsetofK_{1, n}. Let x _{1}, x _{2},…, x _{n}be the successive vertices of C_{n }and e= x _{2 }x_{n }be the chord of C_{n}.The vertices x_{1}, x _{2}, x _{n }forma triangle with the chorde.Here v is the a pexvertex & y _{1}, y _{2},…, y _{n}are pendant verticesofK_{1, n}.
I determine labeling function g: V (G ⊕K_{1, n}) → {F_{0}, F_{1},F_{2},. . . , F_{2n}}, as below.
CaseI:n≡0(mod3).
For all 1 ≤ i ≤ n.
g (x_{i}) =F_{i}.
g(y_{i}) = F_{n+i}.
CaseII:n≡1(mod3).
g (x_{i}) = F_{i}, 1 ≤ i ≤ n.
g (y_{1}) = F_{0},
g(y_{i}) = F_{n+i−1}, 2 ≤ i ≤ n.
From the above labeling pattern i have e_{g}(0)=n and e_{g}(1)=n+1.
Therefore |e_{g}(1)−e_{g}(0)|≤1.
Thus, the graph G ⊕ K_{1, n}is a Fibonacci cordial graph.
Example 6
A Fibonacci cordial labeling of ring sum of C_{7}with one chord and
K_{1, 7}can be seen in Figure 6.
Figure 6 |
Theorem 7
The graph G ⊕ K_{1, n}is a Fibonacci cordial graph for all n ≥5, n∈N,where G is the cycle with twin chords forming two triangles and another cycleC_{n−2}with the edges of C_{n}.
Proof7
Let G be the cycle C_{n }with twin chords,where chords form two triangles and one cycle C_{n−2}.LetV(G⊕K_{1, n})=X_{1}∪ X _{2}. X_{1}={x_{1}, x _{2},…, x _{n}} is the vertex set of C_{n}, e_{1}= x_{n }x_{2}and e_{2}= x_{n }x_{3} are the chords of C_{n}. X_{2}={y= x_{1}, y_{1}, y_{2},…, y_{n}}is the vertex set of K_{1, n},where y_{1}, y_{2},…, y_{n }are pendant vertices and y= x_{1}istheapexvertexofK_{1, n}.Also|V(G⊕K_{1, n})|=2n, |E(G ⊕ K_{1, n})| = 2n + 2.
Take y= x _{1}.Also|V(G⊕K_{1, n})|=2n, |E(G ⊕ K1,n)| = 2n + 1.
I determine labeling function g: V(G ⊕K_{1, n}) → {F_{0}, F_{1},F_{2},. . . , F_{2n}}, as below.
g (x_{1})= F_{1},
g(x_{2})= F_{2},
g (x_{3})= F_{3},
g (x_{n}) = F_{4},
g (x_{i}) = F_{i+1}, 4 ≤ i ≤ n − 1.
g (y_{i}) = F_{n+i}, 1 ≤ i ≤ n.
From the above labeling pattern i have e_{g }(0)=e_{g}(1)=n+1.
Therefore |e_{g}(1)−e_{g}(0)|≤1.
Thus, The graph G ⊕ K_{1, n}is a Fibonacci cordial graph.
Example7
A Fibonacci cordial labeling of ring sum of C_{9 }with twin chords andK_{1, 9}can be seen in Figure7.
Figure 7 |
Conclusion
In this paper i investigate seven new graph which admits Fibonacci cordial labeling.
References
- 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.
- F.Harary,Graphtheory, Addision-wesley,Reading,MA(1969).
- J Gross and J Yellen, Handbook of graph theory, CRC press(2004).
- J. A. Gallian, A dynamic survey of graph labeling, The Electronics Journal of Combinatorics,19(2012),�DS61−260.
- M. Sundaram, R. Ponraj, and S. Somasundram, Prime cordial labeling of graphs,Journal of Indian Acadamy of Mathematics,27(2005),373-390.
- 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.
- 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.
- S. K. Vaidya and P. L. Vihol, Prime cordial labeling for some graphs, Modern Applied Science, 4, No.8 (2010), 119-126.
- 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.
- S. K. Vaidyaa and N. H. Shah, Prime cordial labeling of some wheel related graphs,Malaya Journal of Matematik,4(1)(2013)148156.
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 International License.