International Journal of Innovative Research in Science, Engineering and Technology
MenuISSN ONLINE(2319-8753)PRINT(2347-6710)
ISSN ONLINE(2319-8753)PRINT(2347-6710)
| Dr.S.Meena1, K.Vaithilingam2 Associate Professor of Mathematics, Government Arts College, C.Mutlur, Tamil Nadu, India1 Associate Professor of Mathematics, Government Arts College, C.Mutlur, Tamil Nadu, India2 |
| Related article at Pubmed, Scholar Google |
Visit for more related articles at International Journal of Innovative Research in Science, Engineering and Technology
A graph with vertex set V is said to have a prime labeling if its vertices are labeled with distinct integers 1,2,3 … ð such that for edge ð¥ð¦ 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 helm related graphs. We also discuss prime labeling in the context of some graph operations namely fusion and duplication in Helm ð»ð
Keywords |
| Prime Labeling, Fusion, Duplication |
INTRODUCTION |
| In this paper, we consider only finite simple undirected graph. The graph G has vertex set V = V(G) and edge set E = E(G) . The set of vertices adjacent to a vertex u of G is denoted by N(u) . 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 researchers have studied prime graph for example Fu.H. (1994 P 181-186) [5] Have proved that path Pnon n vertices is a Prime graph. |
| Deretsky.T (1991 P359 – 369) [4] have proved that the Cn on n vertices is a prime graph. Lee.S (1998 P.59- 67) [2] have proved that wheel wn 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 [8] S.K.Vaidhya and K.K.Kanmani have proved the prime labeling for some cycle related graphs. |
II. DEFINITION |
| Definition 1.1 |
Let G = (V(G), E(G)) be a graph with p vertices. A bijection  is called a prime labeling if for each edge  . A graph which admits prime labeling is called a prime graph. |
| Definition 1.2 |
| Fusion: 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 vk of a graph G produces a new graph gk by adding a vertex vki with (vki ) = N(vk) . |
| In other words a vertex vki is said to be a duplication of vk if all the vertices which are adjacent to vk are now adjacent to vki |
| 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 (Path Union) |
Let  be n copies of a fixed graph G. The graph obtained by adding an edge between  is called the path union of G. Definition: 1.6 |
| Definition: 1.6 The helm Hn is a graph obtained from a wheel by attaching a pendant edge at each vertex of the n-cycle. In this paper we have proved that the helm Hn , the graph obtained by fusing the vertices v1 and vk on the rim, the graph obtained by duplication of any vertex of Hn , the graph obtained by switching of any vertex of Hn and the graph obtained by the path union of two copies of Hn by a path of length k are all prime graphs. |
III. THEOREM |
| Theorem: 1 |
| The helm Hn is a prime graph. |
| Proof: |
 |
| We consider two cases, |
 |
| Then f admits prime labeling. |
| Case (ii): |
 |
| Then f admits prime labeling. |
| Thus Hn is a prime graph. |
| Theorem 2: |
| The graph obtained by fusing the vertex v2 with v1 (or any two consecutive vertices) in a helm graph Hn is a prime graph. |
 |
| Theorem 3: |
| The graph obtained by fusing the vertex v1 with v3 in a helm graph Hn is a prime graph. |
| Proof: |
 |
 |
 |
| Then f admits prime labeling. |
| Case (ii) |
| If n = 3k − 1 but 2n − 1 is not a multiple of 5 and not a multiple of 7, then in the above labeling f defined in case (i) interchange the labels of v2 and v2 ′ . The resulting labeling f is a prime labeling. |
| Case (iii) |
| If n = 3k − 1 but 2n − 1 is a multiple of 5 but not a multiple of 7, then in the above labeling f defined in case (i) interchange the labels of v2 and v2 ′ and also interchange the labels of v3 and v3 ′ . The resulting labeling fII is a prime labeling. |
| Case (iv): |
| When n = 3k − 1 and 2n − 1 is a multiple of 5 and 2n − 1 is a multiple of 7, |
 |
| Then f admits prime labeling. |
| Case (v): |
| If n = 3k − 1 and 2n − 1 is not a multiple of 5 and also a multiple of 7, then in the above labeling f defined in case (iv) interchange the labels of v5 and v5 ′ . The resulting labeling fIII is a prime labeling. |
| Case (vi) |
| If n ≠ 3k − 1 but 2n − 1 is a multiple of 5 and also a multiple of 7, then in the above labeling f defined in case (iv) interchange the labels of v3 and v3 ′ . The resulting labeling f(iv) is a prime labeling. |
| Case (vii): |
| If n ≠ 3k − 1 and 2n− 1 is not a multiple of 5 but 2n − 1 is a multiple of 7, then in the above labeling f defined in interchange the labels of v3 and v3 ′ , v5 and v5 ′ . The resulting labeling f(v) is a prime labeling. |
| Case (viii) |
| If n ≠ 3k − 1 and 2n − 1 is a multiple of 5 but not a multiple of 7, then in the above labeling f defined in case (i) interchange the labels of v5 and v5 ′ . The resulting labeling f(vi) is a prime labeling. Thus in all the cases v4 admits prime labeling, hence v4 is a prime graph. |
| Theorem 5: |
| The graph obtained by fusing the vertex v1 with v5 in a helm graph hn is a prime graph |
| Proof: |
 |
| Then f admits prime labeling. |
| Case (ii) |
| If n = 3k − 1 but 2n − 1 is not a multiple of 7, then in the above labeling f defined in case (i) interchange the labels of v2 and v2 ′ and the label v6 and v6 ′ . The resulting labeling fIis a prime labeling. |
| Case (iii) |
| If either n = 3k − 1or n ≠ 3k − 1 but 2n − 1 is a multiple of 7. |
 |
III. EXAMPLES |
| Example for theorem 1: |
 |
 |
| Example for theorem 2: |
 |
 |
| Example for theorem 3: |
 |
| Example for theorem 4: |
 |
| Example for theorem 5: |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
| Theorem 10: |
 |
 |
ACKNOWLEEDGEMENT |
| The author wish to thank University grant commission and this work was supported by UGC minor research project. |
References |
|