Prime Labeling Of Friendship Graphs

Prime Labeling Of Friendship Graphs

Dr. S. Meena

Associate Professor of Maths Govt. Arts College, C.Mutlur-608102

Chidambaram.

K. Vaithilingam

Associate Professor of Maths Govt. Arts College, C.Mutlur-608 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 365-368). [2] Many researches have studied prime graph for example in Fu.H.(1994 P 181-186) [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.59-67) [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 P205-209) [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 un-1 or vn-1) 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 j-1

f (vi) = i-2 for j+2i k-1 f (v) =k-1

f (vj+1) = k-2

f (vi) =i-1 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 k-1

f (vk) = 2n+1

f (vi) = i-1 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 k-1 f (vk) =p

f (vi) = i-1 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:

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

2. A.Tout A.N.Dabboucy and K.Howalla Prime labeling of graphs.

   Nat.Acad.Sci letters 11 (1982)365-368

3. S.M.lee, L.Wui and J.Yen on the amalgamation of Prime graphs.

   Bull.Malaysian Math.Soc.(Second Series) 11, (1988) 59-67.

4. To Dretsky etal on Vrtex Prime labeling of graphs in graph theory, Combinatories and applications vol.1 J.Alari (Wiley. N.Y. 1991)299-359

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

6. Sundaram M.Ponraj & Somasundaram.S.(2006) on prime labeling conjecture Ars Combinatoria 79 205-209

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

8. S.K.Vaidya and K.K.Kanmani Prime labeling for some cycle related graphs Journal of Mathematics Research vol.2. No.2.May 2010 (98-104)