 Open Access
 Total Downloads : 1452
 Authors : Dr. S. Meena, K. Vaithilingam
 Paper ID : IJERTV1IS10257
 Volume & Issue : Volume 01, Issue 10 (December 2012)
 Published (First Online): 28122012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Prime Labeling Of Friendship Graphs
Dr. S. Meena
Associate Professor of Maths Govt. Arts College, C.Mutlur608102
Chidambaram.
K. Vaithilingam
Associate Professor of Maths Govt. Arts College, C.Mutlur608 102
Chidambaram.
Abstract:
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 in fan Fn
Keywords: Prime Labeling, Fusion, Duplication.
1. 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 f:V(G)
{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()
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 (Friendship graph)
The friendship graphs Tn is a set of n triangles having a common central vertex.
Theorem.1
The friendship graph Tn is a prime graph Proof:
Let V (Tn) = { v1, v2, .. v2n+1} with v1 as the centre vertex.
E (Tn) = { v1 vi /2 i 2n+1} U {v2i v2i+1 / 1 i n} Define a labeling f: v(Tn) {1,2, 2n+1} as follows:
f (vi) = i for 1 i 2n+1 Clearly f is a prime labeling
Tn is a prime graph.
Theorem.2
The graph obtained by identifying any two vertices other than centre vertex of a friendship graph Tn is a prime graph.
Proof:
Let V (Tn) = { v1, v2, .v2n+1}
E (Tn) ={v1 vi / 2 i 2n+1}U{v2i v2i+1 / 1i n} Where v1 is the centre vertex of the friendship graph.
Let the vertex vj be fused with uk where 2 j k 2n+1 and let the newe vertex be v and let Gv be the graph obtained by fusion of vi and vj
Now define a function f: V(Gv) {1,2, 2n} as follows f (v1) = 1
f (vi) = i for 2 i j1
f (vi) = i2 for j+2i k1 f (v) =k1
f (vj+1) = k2
f (vi) =i1 for k+1 i2n Clearly f is a prime labeling. Thus Gv is a prime graph
Example
Consider T5 and let Gv be the graph obtained by identifying vj and vk where j=4, K=8.
9
v10
10
v11
8 v9
v2 2
v1
7 v4 = v8
1
v3 3
6 v5
v6 4 v7
5
Theorem.3
The graph obtained by duplicating a vertex vk except the centre vertex of the friendship graph Tn produces a prime graph.
Proof:
Let V(Tn) = {v1, v2,v2n+1} with v1 as the centre vertex and let E (Tn) = {v1 vi / 2i2n+1}U{ v2i v2i+1 / 1i n}
Let GR be the graph obtained by duplicating the vk by the new vertex vk1.
Case (i):
If k is odd
Define a labeling f: V(GK) {1,2, .. 2n+2} as follows: f (v1) = 1
k
v (vi) = i+1 for 2 i 2n+1 f (v 1) = 2
Then clearly f is a prime labeling.
Case (ii):
If k is even
Define a labeling f: V(Gk) {1,2,..2n+1} as follows: f (v1) = 1
k
f (vi) = i for 1 i 2n+1 f (v 1) = 2n+2
Then clearly f is a prime labeling. Thus Gk is a prime graph .
Example:
Consider T6 and let Gk be the graph obtained by duplicating vk and let vk1
be the new vertex. K=7
8 v9
9
v10
10
v11
v2 2
v1
7 v4 = v8
1
v3 3
K = 10
6 v5
14
v6 4 v7
5
v101
9 v9
10
v10
11
v11
v12 12
8 v8
7 v7
v1 v13 13
1 v2 2
v6
v5 v4
v3 3
6
5 4
Theorem.4
The graph obtained by switching any vertex vk in a friendship graph Tn produces a prime graph.
Proof:
Let V (Tn) ={ v1,v2, .. v2n+1}
E (Tn) = {v1 vi / 2i2n+1} U { v2i v2i+1 / 1i n} Where v1 is the centre vertex of Tn
Let Gk be the graph obtained by switching any arbitrary vertex vk in Tn.
If k=1 then the function
f: v(G1){1,2,2n+1} defined by f(vi) = i for 1i2n+1 is a prime labeling for G1
Assume that k>1
Case (i):
2n+1 is prime
Define a labeling f: v(Gk){1,2,.2n+1} as follows: f (vi) = i for 1 i k1
f (vk) = 2n+1
f (vi) = i1 for k+1 i 2n+1 Then f admits prime labeling. Case (ii):
If 2n+1 is not prime let P be the largest prime number such that p< 2n+1 Define a labeling f: V(Gk){1, 2, ..2n+1} by
f (vi) = i for 1 i k1 f (vk) =p
f (vi) = i1 for k+1 i p
f (vi) = i for p+1 i 2n+1 then f admits prime labeling Thus Gk is a prime graph.
Example.1
Let G5 be the graph obtained by switching vertex v5 in T6 (2n+1 is not prime)
10 v11
11
v12
12
v13
v2 2
9 v10
10 v9
v3 3
v4 4
v8
v7 v6
7
6 5
Example.2
Let G7 be the graph obtained by switching a vertex v7 in T7 (2n+1 is not prime)
2 3
V3
V2
15 v15
V4 4
14 v14
12 v13
11 v12
V11 10
V9
V10
9 8
V5 5
V6 6
V7 13
V8 7
Remark:
Path union of two copies of Tn is not prime. Since in the graph obtained by path union of two copies of Tn the number of vertices is 4n+2
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 Vrtex 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) 181186.

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)