 Open Access
 Total Downloads : 1406
 Authors : Dr. S. Meena, K.Vaithilingam
 Paper ID : IJERTV1IS9313
 Volume & Issue : Volume 01, Issue 09 (November 2012)
 Published (First Online): 29112012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Prime Labeling For Some Fan Related Graphs
Dr. S. Meena
Associate Professor of Maths Govt. Arts College, C.Mutlur608102
Chidambaram.
Abstract:
K.Vaithilingam
Associate Professor of Maths Govt. Arts College, C.Mutlur608 102
Chidambaram.
A graph with vertex set V is said to have a prime labeling if its vertices are labeled with distinct integer 1,2,3 such that for edge xy the labels assigned to x and y are relatively prime. A graph which admits prime labeling is called a prime graph. In this paper we investigate prime labeling for some fan related graphs. We also discuss prime labeling in the context of some graph operations namely fusion and duplication, Switching in fan Fn
Keywords: Prime Labeling, Fusion, Duplication and Switching.

Introduction:
In this paper, we consider only finite simple undirected graph. The graph G has vertex set and edge set . The set of vertices adjacent to a vertex u of G is denoted by . For notations and terminology we refer to Bondy and Murthy [1].
The notion of a prime labeling was introduced by Roger Entringer and was discussed in a paper by Tout. A (1982 P 365368). [2] Many researches have studied prime graph for example in Fu.H.(1994 P 181186) [5] have proved that path Pn on n vertices is a Prime graph.
In Deretsky.T(1991 p359 369) [4] have proved that the on n vertices is a prime graph. In Lee.S (1998 P.5967) [2] have proved that wheel is a prime graph iff
n is even. Around 1980 Roger Etringer conjectured that all tress have prime labeling which is not settled till today. The prime labeling for planner grid is investigated by Sundaram.M(2006 P205209) [6]
In (2010) S.K.Vaidhya and K.K.Kanmani have proved the prime labeling for some cycle related graphs [7]
Definition 1.1
Let G = (V(G), E(G)) be a graph with p vertices. A bijection {1,2,p} is called a prime labeling if for each edge e=uv, gcd{f(u), f(v)}=1. A graph which admits prime labeling is called a prime graph.
Definition 1.2
Let u and v be two distinct vertices of a graph G. A new graph G1 is constructed by identifying (fusing) two vertices u and v by a single vertex x in such that every edge which was incident with either u or v in G now incident with x in G.
Definition : 1.3
Duplication: Duplication of a vertex of a graph G produces a new graph by adding a vertex with N( )=N( )
In other words a vertex is said to be a duplication of if all the vertices which are adjacent to are now adjacent to
In this paper we prove that the graphs obtained by identifying any two vertices of degree 2 in the fan graph Fn and two vertices which are adjacent to vertices of degree 2 (u2 and v2 or un1 or vn1) and the graph obtained by duplication the vertex of degree 2 admit prime labeling.
Definition: 1.4
Switching: A vertex switching of a graph G is obtained by taking a vertex v of G, removing the entire edges incident with v and adding edges joining v to every vertex which are not adjacent to v in G.
Definition: 1.5 (Fan graph)
A fan graph obtained by joining all vertices of Fn, n 2 is a path Pn to a further vertex, called the centre.
Thus Fn contains n+1 vertices say C, and (2n1) edges, say , and , 1 .
Theorem 1:
The graph Obtained by duplicating arbitrary vertex of fan Fn is a Prime graph.
Proof:
Let G = Fn be the graph
Let V(G) be
and edge of G E(G) = { , } U { , 1 } Let be the vertex duplicated to . Let the new graph be G1
Define a labeling f by
f: as follows
Case (i)
For n 3k+1, K is an integer. Let f(c) = 1
1
then f admits prime labeling. T herefore G1 is prime graph. Example F5 Vertex duplication of
Case (ii)
For n= 3k+1 k=2,4,6 Define f as
f(c)=1
f()=2
f( )=3
f( )=4 f( ) = i+2, 3
Then of admits prime labeling G1 is a prime graph
Example F7 Vertex duplication of
Theorem 2:
The switching of any vertex in a fan graph produces a Prime graph for n=k+1 k is a Prime numbers
Proof:
Let G = and be the successive vertices of and let C be the centre vertices of
Define a labeling f: V {1,2.n+1} as follows f(c)=1
f( )=i 2
f( )=n+1
then f results a prime labeling Therefore is a prime graph
In general for the above value of n, we can generalize the switching of vertex as for = 1,2n we get the prime labeling.
Here we consider the new graph as When the vertex switching is
Define f: {1,2.n+1} As followed When i=2 Switching Let f(c)=1
f( )=i1 for 3
f( )=n
f( )=n+1
In general fix the number 1 for the centre vertex and assign the remaining number from the next vertex of the switching vertex in clockwise direction, then f permits prime labeling.
Therefore resulting graph is a Prime graph Example F5 Vertex Switching
Let be the vertex duplicated to . Let the new graph be G1
Define a labeling f by
f: as follows Let f(c) = 1
for 3 .
then f admits prime labeling. Therefore is a prime graph Example: Duplication of in F6
Let be the vertex duplication to . Let the new graph be
Now define a labeling f: as follows Let
f(c) = 1
for 1 .
Then f admits prime labeling. Therefore is a prime graph
Example: Vertex duplication in a fan graph F6
Theorem 5:
The duplication of a vertex in a fan graph produces a prime graph.
Proof:
Let be fan graph.
Let V(G) = and edge of G E(G) = { , } U { , 1 }
Let be the vertex duplication to . Let the new graph be
Now define a labeling f: as follows
Case (1)
For
f(c) = 1
for 2 .
Then f admits prime labeling.
For , the is a prime graph
Example: Vertex duplication of F6
Case (2)
For
f: as follows
for
Then f admits prime labeling.
For , the is a prime graph
Example: Vertex duplication of in F7.
Theorem 6:
The duplication of the vertex in a fan graph produces a prime graph.
Proof:
Let be fan graph.
Let V(G) = and edge of G E(G) = { , }
U { , 1 }
Let be the vertex duplication to . Let the new graph be
Now define a labeling f: as follows
for
Then f admits prime labeling. Therefore is a prime graph
Example Duplication of in F6
Theorem 7:
The duplication of any vertex , k is even in a fan graph produces a prime graph.
Proof:
Let be fan graph.
Let V(G) = and edge of G E(G) = { , } U { , 1 }
Let is even be the vertex duplicated to producing a new graph .
Now define a labeling f: as follows
for
Then f admits prime labeling. Therefore is a prime graph
Example
Theorem 8:
The duplication of any vertex
, k is odd in a fan graph
produces a prime graph.
Proof:
Let be fan graph.
Let V(G) =
and edge of G be E(G) = {
, }
U { , 1 }
Let duplicated to .
For the value define a new graph as
Now define a labeling f: as follows
for
Then f admits prime labeling. Therefore is a prime graph
Theorem 9:
In a fan graph fusion of with produces a prime graph.
Proof:
Let be fan graph.
Let a new graph obtained by fusion with .
Now define a labeling f: as follows
for
Then f admits prime labeling. Therefore is a prime graph
Example Fusion of with v1 in F7
Theorem 10:
Fusion of with in a fan graph produces a prime graph.
Proof:
Let be fan graph.
Let and edge of G be E(G) = { , } U { , 1 }
Let a new graph obtained by fusion with .
Now define a labeling f: as follows For
i=1,2
Then f admits prime labeling. Therefore is a prime graph
Example
Theorem 11:
Fusion of with in a fan graph produces a prime graph.
Proof:
Let be fan graph.
Let and edge of G be E(G) = { , } U { , 1 }
Let a new graph obtained by fusion of vertex with .
Now define a labeling f: as follows
,
,
Then f admits prime labeling.
Therefore fusion of with produces prime graph.
Example: Fusion of with in a fan graph
Theorem 12:
Fusion of with in a fan graph produces a prime graph for the prime n .
Proof:
Let be fan graph.
Let and edge of G be E(G) = { , } U { , 1 }
Let a new graph obtained by fusion of vertex with .
Now define a labeling as follows
Then f admits prime labeling.
Therefore fusion of with produces prime graph.
Example: Fusion of with in a fan graph
Theorem 13:
Fusion of with in a fan graph produces a prime graph for the prime is odd .
Proof:
Let be fan graph.
Let and edge of G be E(G) = { , } U { , 1 }
Let a new graph obtained by fusion of vertex
Now define a labeling as follows
Then f admits prime labeling.
Therefore fusion of with produces prime graph.
Example fusion of with
Theorem 14:
Fusion of a vertex with , (k even) in a fan graph prime produces a prime graph.
Proof:
Let be fan graph.
Let and edge of G be E(G) = { , } U { , 1 }
Let a new graph obtained by fusion of vertex with .
Now define a labeling as follows
Case (i)
For
Then f admits prime labeling. Therefore is a prime graph. Case (ii)
For
Then f admits prime labeling. Therefore is a prime graph.
Example
Fusion in vertex (k even) with , n prime General case:
Specific case:
References:

J.A.Bondy and U.S.R.Murthy, Graph Theory and Applications(North Holland).Newyork (1976)

A.Tout A.N.Dabboucy and K.Howalla Prime labeling of graphs.
Nat.Acad.Sci letters 11 (1982)365368

S.M.lee, L.Wui and J.Yen on the amalgamation of Prime graphs. Bull.Malaysian Math.Soc.(Second Series) 11, (1988) 5967.

To Dretsky etal on Vertex Prime labeling of graphs in graph theory,
Combinatories and applications vol.1 J.Alari (Wiley. N.Y. 1991)299359

H.C. Fu and K.C.Huany on Prime labeling Discrete Math, 127 (1994) 181 186.

Sundaram M.Ponraj & Somasundaram.S.(2006) on prime labeling conjecture
Ars Combinatoria 79 205209

Gallian J. A(2009), A dynamic survey of graph labeling. The Electronic Journal of Combinations 16 # DS6

S.K.Vaidya and K.K.Kanmani Prime labeling for some cycle related graphs

Journal of Mathematics Research vol.2. No.2.May 2010 (98104).