Prime Labeling For Some Fan Related Graphs

Prime Labeling For Some Fan Related Graphs

Dr. S. Meena

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

Chidambaram.

Abstract:

K.Vaithilingam

Associate Professor of Maths Govt. Arts College, C.Mutlur-608 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.

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 {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 un-1 or vn-1) 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 (2n-1) 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( )=i-1 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:

   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 Vertex 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).