INTRODUCTIONGraph theory was introduced by Leonhard Euler in 1736.

The first solution of graph theory was the bridge of Konigsberg problem. The theory of graph is more powerful tool for several areas. Namely, network sectors, geometrical aspects and etc.

Labeling of a graph is the allocation of labels, commonly appear for integers, to the edges (or) vertices (or) both of a graph. All the labels using in graphs are unique. We considered only vertex labeling throughout this dissertation.In 1967, Alex Rosa introduced the concept of origins to labeling of several problems. They exhibited the delicacy of combinatorial constructions and interesting problems .

The notion of Prime labeling for graph applications originated with Roger Entringer and was introduced in a paper by Tout et al in the early 1980’s and since it is an active field of research for many Scholars.The idea is to label the vertices of a graph in such a way the greatest common divisor on labels for every pair of adjacent vertices must be one. It is called Prime labeling.In this dissertation, we investigate the notion of prime labeling and prime graphs.CHAPTER – IFUNDAMENTAL DEFINITIONS AND EXAMPLESDefinition 1.1:A “Graph” G is an well-ordered triple (V(G),E(G),?G) consisting of a non-empty set V(G) of vertices, a set E(G), disjoint from V(G) of edges and an incident function ?G that linked with each edge of G an unordered pair of vertices of G.

If e is an edge and u and v are vertices such that ?Ge=uv then e is said to link u and v. The vertices u and v are called the ends of e.Example 1.1: v1 e1 e3 v2 e2 v3 Definition1.2:If the vertices of the graph are assigned values subject to assured conditions then it is well-known as (vertex) graph “labelling”.Example 1.

2: 1 v1 2 v2 4 v4 3 v3Definition 1.3:A “Walk” in G is a finite non-null sequence w=v0e1,v1e2,….,epvp whose terms are alternately vertices and edges, such that for 1?t?k, the ends of es are vt-1 and vt. we say that w is a walk from v0 to vp.

The vertices v0,v1,….,vp are distinct, w is called a “Path”. Example 1.

3: v1 v2 v3 v4 v5 v6Definition 1.4:”A closed path is also known as “Cycle”. v1 v2 v6 v3 v4 v5 Definition 1.7:A vertex of a graph is known as “Pendent” if its neighborhood contains accurately one vertex”.Definition 1.

8:Let G be a graph. An edge e of a graph G is said to be “Pendant edge” if and only if it is incident on a pendant vertex.Definition 1.

9: A “Wheel graph” is a graph created by connecting a single vertex to all the vertices of a cycle Cn.Example 1.4: v1 v4 v2 v3 Definition 1.10:The “Helm” Hn is the graph obtained from the wheel Wn=Cn+K1 by attaching a pendant edge at each vertex of cycle Cn.

Example 1.5 v5 v1 v4 v2 v3 v6 v7Definition 1.11:For a graph G the “Splitting graph” S of G is obtained by adding a new vertex v corresponding to each vertex v of G such that N(v)=N(u).Example 1.6: v’ v1 v2 v3 v4 v5 v6 v v1′ v2′ v3′ v4′ v5′ v6′ Definition: 1.12:A bipartite graph with bipartite (v1,v2) is called a “Complete bipartite graph”, if every vertex of v1 is adjacent to every vertex of v2.

If ?v1?=m and ?v2?=n, such a graph is denoted by Km,n.Example 1.7: (ii) v1 v2 v3 v4 v5 v6 Definition 1.

13:The “Sunlet graph Sn” is the graph obtained from a cycle Cn attaching a pendent edge at each vertex of the n-cycle.Example 1.8: v1 v2 u1 u2 u4 u3 v4 v3Definition 1.

6:For a vertex v in the graph G, the “neighbourhood” of v is the set of all vertices in G which are adjoining to v and its denoted by N(v)..Definition 1.14:A “Flower” is a graph obtained from a helm by joining each pendant vertex to the central vertex of the helm”.Example 1.9: u1 v1 v6 u6 u2 v0 v5 v2 u5 v3 v4 u3 u4 Definition 1.

15:A graph is obtained by replacing each edge of K1,t by path Pn of length n on n+1 vertices is called “One point union” for t copies of path Pn. We shall denote such graph G by Pnt.Definition 1.16:”The Friendship graph Fn is one-point union of n copies of cycle C3.”Example 1.

10: v2 v3 v1 v0 v4 v8 v5 v7 v6Definition 1.17:”Bistar” is the graph obtained by joining the apex vertices of two copies of star K1,n.Example 1.11: u1 u2 u3 u4 u v v1 v2 v3 v4Definition 1.18:”Duplication of a vertex” v of a graph G produces a new graph G? by adding a new vertex v? such that N(v?)=N(v). Definition 1.

19An “Independent set of vertices in a graph G is a set of mutually non-adjacent vertices. Definition 1.20An “SF(n,m)” is a graph consisting of a cycle Cn,n?3 and n set of m independent vertices where each set joins each of the vertices of Cn.”Example 1.12: u1 u2 v1 v2 v3 v4 u3 u4 Definition 1.

21:Let u and v be two distinct vertices of a graph G. A new graph Gu,v is constructed by “Identifying(fusing)” two vertices u and v by a single new vertex x such that every edge which was incident with either u or v in G is now incident with x in Gu,v.CHAPTER – IIPRIME LABELING OF SOME SPECIAL GRAPHSDefinition 1.5:Let G=(V(G),E(G)) be a graph with n vertices. A bijecion f:V?{1,2,.

..,n} is called a “Prime labelling”, if for each edge e=uv, gcd(fu,f(v))=1. A graph which admits prime labeling is called a “Prime graph”. 3 1Example 1.

3: v1 v2 2 5 4 v3 v4 v5Theorem 2.1The Flower graph Fln admits a prime labeling.Proof:We know that the flower graph Fln contains three types of vertices.Let v be the apex vertex of degree 2n.vp for p=1,2,3,..

.,n be the vertices of degree 4up for p=1,2,3,…

,n be the vertices of degree 2Let g:V?{1,2,3,…,|V|} be a bijective function and Define the label g by, gv=1 gvp=2p+1 1?p?n gup=2p 1?p?nThere exist a bijective function g:V?{1,2,3,…,|V|} such that for each e=u,v?E.Also we have gcdgu,gv=1.Therefore the flower graph Fln admits a prime labeling.Example 2.

1Consider a flower graph Fl6. u1 2 3 v1 v2 5 u2 4 12 u6 1 v v3 7 13 v6 u3 6 v5 11 v4 9 10 u5 8 u4 Define the label g by, gv=1 gvp=2p+1 1?p?n gup=2p 1?p?nThe labels are gv1=21+1=3 gv2=22+1=5Similarly, gv3=7,gv4=9, gv5=11, gv6=13, gu1=21=2, gu2=22=4, Similarly, gu3=6,gu4=8,gu5=10, gu6=12 Hence gcdgv,g(v1)=gcd1,3=1 gcdgv,g(v2)=gcd1,5=1 gcdgv,g(v3)=gcd1,7=1 gcdgv,g(v4)=gcd1,9=1Similarly if we proceed in this way all the vertices are satisfied with the GCD of 1.Therefore the Flower graph Fl6 admits a prime labeling.Theorem 2.2The Bistar Bn,n admits a prime labeling.Proof:First we consider the two copies of K1,n.

Let vpand up for p=1,2,3,…,n be the corresponding vertices of each copy of K1,n with apex vertices u and v.

Let e=vvp, ep’=uupand e=uv of bistar graph.Then VBn,n=2n+2 and EBn,n=2n+1Let g:V?{1,2,3,…,|V|} be a bijective function and Define the label g by, gu=1, gv=2 gup=2p+2 1?p?n gvp=2p+1 1?p?nIn consideration of the above labeling pattern, The Bistar Bn,n admits a prime labeling.Exampleb2.2: u4 10 u5 12 u6 14u1 4 u2 6 u3 8consider the Bistar B6,6 2 2V 1 uv1 3 v2 5 v3 7 v4 9 v5 11 v6 13 Define the label g by, gu=1, gv=2 gup=2p+2 1?p?n gvp=2p+1 1?p?nThe labels are gv1=21+1=3 gv2=22+1=5 Similarly, gv3=7,gv4=9, gv5=11, gv6=13, gu1=21+2=4, gu2=22+2=6, Similarly, gu3=8,gu4=10,gu5=12, gu6=14 Hence gcdgv,g(v1)=gcd2,3=1 gcdgv,g(v2)=gcd2,5=1 gcdgu,g(u1)=gcd1,4=1 gcdgu,g(u2)=gcd1,6=1 gcdgu,g(v)=gcd1,2=1Similarly if we proceed in this way all the vertices are satisfied with the GCD of 1.Therefore the Bistar B6,6 admits a prime labeling.

Theorem 2.3:The Splitting graph of star graph admits a prime labeling.Proof:Let vp for p=1,2,3,…,n be the vertices of star graph K1,n and v be the apex vertex.Let us consider G be the Splitting graph of K1,n and newly added vertices are vp’ for p=1,2,3,…,n with K1,n to form G.Let g:V?{1,2,3,…,|V|} be a bijective function and Define the label g by, gv=1, gv’=2 gvp=2p+1 1?p?n gvp’=2p+2 1?p?nIn consideration of the above labeling pattern,The splitting graph of star graph admits a prime labeling.

Example 2.3:Consider a Splitting graph K1,6Define the label g by, gv=1, gv’=2 gvp=2p+1 1?p?n gvp’=2p+2 1?p?n v’ 2 v1 3 v2 5 v3 7 v4 9 v5 11 v6 13 v 1 v1′ 4 v2′ 6 v3 ‘ 8 v4′ 10 v5′ 12 v6′ 14The labels are gv1=21+1=3 gv2=22+1=5 Similarly, gv3=7,gv4=9, gv5=11, gv6=13, g v1’=21+2=4, gv2’=22+2=6, Similarly, gv3’=8,gv4’=10,gv5’=12, gv6’=14 Hence gcdgv,g(v1)=gcd1,3=1 gcdgv,g(v2)=gcd1,5=1 gcdgv’,g(v2′)=gcd2,4=1 gcdgv’,g(v2′)=gcd2,6=1 gcdgv,g(v’)=gcd1,2=1Similarly if we proceed in this way all the vertices are satisfied with the GCD of 1.Therefore the Splitting graph K1,6 admits a prime labeling.Theorem 2.

4:The friendship graph Fn admits a prime labeling.Proof: Consider a friendship graph Fn with n copies of cycle C3.Let v be the apex vertex, and vp for p=1,2,3,…,2n be the other vertices of Fn and eq for q=1,2,3,…,3n be the edges of Fn.Let g:V?{1,2,3,…,|V|} be a bijective function and Define the label g by, gv=1 gvp=p+1 1?p?nThere exist a bijective function g:V?{1,2,3,…,|V|} such that for each e=u,v?E.Also we have gcdgu,gv=1.

Therefore the friendship graph Fn admits a prime labeling.Example 2.4: Consider a friendship graph F4. v2 3 4 v3 v1 2 v 5 v4 v8 9 1 6 v5 v7 8 7 v6Define the label g by, gv=1, gvp=p+1 1?p?n The labels are, gv1=1+1=2 gv2=2+1=3Similarly, gv3=5,gv4=5, gv5=6, gv6=7, Hence gcdgv,g(v1)=gcd1,2=1 gcdgv,g(v2)=gcd1,3=1 gcdgv1,g(v2)=gcd2,3=1 gcdgv3,g(v4)=gcd4,5=1Similarly if we proceed in this way all the vertices are satisfied with the GCD of 1.Therefore the Friendship graph F4 admits a prime labeling.

Theorem 2.5:The graph SFn,1 admits a prime labeling.Proof:Let G denote the graph SF(n,1).

Let vp for p=1,2,3,…,n be the vertices of the cycle SF(n,1)and vq’ for q=1,2,3,…,n be the vertices joining the corresponding vertices vq. Here p=2n and q=2nLet g:V?{1,2,3,…,|V|} be a bijective function and Define the label g by, gvq=2q-1 for q=1,2,3,…,n fvq’=2q for q=1,2,3,…,nThere exist a bijective function g:V?{1,2,3,…,|V|} such that for each e=u,v?E.Also we have gcdgu,gv=1.

Therefore the graph SF(n,1) admits a prime labeling.Example 2.5:Consider the graph SF(6,1) v1′ 2 12 v6′ 111 v1 v6 43v29v5 v2′ v5′ 10 75 v3 v486 v3′ v4’Define the label g by, gvq=2q-1 for q=1,2,3,…,n gvq’=2q for q=1,2,3,…,nThe labels are gv1=21-1=1 gv2=22-1=3Similarly, gv3=5,gv4=7, gv5=9, gv6=11. g v1’=21=2, g v2’=22=4Similarly, g v3’=6,g v4’=8 g v5’=10,g v6’=12 Hence gcdgv1,g(v1′)=gcd1,2=1 gcdgv2,g(v2′)=gcd3,4=1 gcdgv3,g(v3′)=gcd5,6=1 gcdgv4,g(v4′)=gcd7,8=1Similarly if we proceed in this way all the vertices are satisfied with the GCD of 1.Therefore the graph SF(6,1) admits a prime labeling.

CHAPTER – III PRIME LABELING FOR SOME SUNLET RELATED GRAPHSProposition 3.1:The Sunlet graph Sn is prime graph.Proof:Consider a Sunlet graph Sn with 2n vertices.Vertices and Edges of a Sunlet graph is defined byV(Sn)={vp,up/p=1,2,…,n}E(Sn)={vpup/1?p?n}?{vpvp+1/1?p?n-1}?{v1vn}Here |V(Sn)|=2n when n is both even and odd.

Let g:V?{1,2,3,…,|V|} be a bijective function and Define the label g by, gvp=2p+1 ,1?p?n-1 gup=2p ,1?p?nIn view of each edge e=vpvp+1?G, Also we have gcdgvp,gvp+1=1.And e=vpup?G, Also we have gcdgvp,gup=1.Therefore g admits a prime labeling.Thus the Sunlet graph Sn is prime graph.Example 3.

1Consider the Sunlet graph S4 u1 u2 v1 v2 v3 v4 u3 u4 2 4 1 3 5 7 6 8We define the labels are using by the idea of above theorem, hence we get gv1=1, gv2=3,gv3=5,gv4=7.And gu1=2, gu2=4,gu3=6,gu4=8And each edge of Sunlet graph e=v1,v2?G,Also we have gcdgvp,gvp+1=1.And e=vpup?G, Also we have gcdgvp,gup=1.

Similarly all the vertices satisfied by GCD of 1.Therefore The Sunlet graph S4 is prime graph.Proposition 3.2The graph obtained by fusing any two successive vertices in a Sunlet graph Sn is prime graph.Proof:Consider a Sunlet graph Sn with 2n vertices.Vertices and Edges of a Sunlet graph is defined by V(Sn)={vp,up/p=1,2,…,n}E(Sn)={vpup/1?p?n}?{vpvp+1/1?p?n-1}?{v1vn}Here, |V(Sn)|=2n Let G be the graph obtained after fusion of two vertices.

VG=2n-1Case (i):When fusing any two successive vertices one in vp and another one is up of Sunlet graph Sn. Let g:V?{1,2,3,…,2n-1} be a bijective function and Define the label g by, gv1=1 v1 is a new vertex gvp=2p+1 2?p?n-1 gup=2p 1?p?n-1Case (ii):When fusing any two successive vertices up of Sunlet graph Sn.Let g:V?{1,2,3,…,2n-1} be a bijective function and Define the label g by, gv1=2 v1 is a new vertexafter fused gup=1,3 where up are pendant vertices incident with v1 gvp=2p+1 2?p?n-1 gup=2p 2?p?n-1Then for each g admits a prime labeling.Hence G is prime graph.Example 3.2:Consider the Sunlet graph S6 u1 v6v2 u6 v1 u2 v5v4 u5 v3 u3 u4 3 1 4 2 5 11 8 7 6 9 10Therefore we seen the above example we get, thus the graph obtained by fusing any two successive vertices in a Sunlet graph S6 is a prime graph.

Proposition 3.3:The graph obtained by fusing any two non-successive vertices in a sunlet graph Sn is a prime graph.Proof:Consider a Sunlet graph Sn with 2n vertices.

Vertices and Edges of a Sunlet graph is defined by V(Sn)={vp,up/p=1,2,…,n} E(Sn)={vpup/1?p?n}?{vpvp+1/1?p?n-1}?{v1vn}Here |V(Sn)|=2n when n is both even and odd.Let G be the graph obtained after fusion of two non-successive vertices in Sn. VG=2n-1Case (i):When fusing any two non-successive vertices one in vp and another one is up of Sunlet graph Sn.

Let g:V?{1,2,3,…,2n-1} be a bijective function and Define the label g by, Take gv1=1 where v1 is a new vertex gup=2, upincident with v1 gvp=3, vpincident with v1 gvp=2p+1, 2?p?n-1 gup=2p , 1?p?n-1Case (ii):When fusing any two non-successive vertices in up of Sunlet graph Sn.Let g:V?{1,2,3,…,2n-1} be a bijective function and Define the label g by, gu1=2 v1 is a new vertex gvp=2,3 where up incident with up gvp=2p+1 2?p?n-1 gup=2p 2?p?n-1 Case (iii):When fusing any two non-successive vertices in vp of Sunlet graph Sn.Let g:V?{1,2,3,…,2n-1} be a bijective function and Define the label g by, gv1=1 v1 is a new vertex gvp=2,3 where vp incident with v1 gvp=2p+1 2?p?n-1 gup=2p 2?p?n-1Then for each g admits a prime labeling.Hence G is prime graphExample 3.3: Consider the Sunlet graph S6 u1 u8 v1 u2 v8 v2 u7 v7 v3 u3 v6 v4 v5 u4 u6 u5 14 12 13 15 3 1 10 11 2 5 9 7 4 8 6Therefore we seen the above example we get, thus the graph obtained by fusing any two non-successive vertices in a Sunlet graph S8 is a prime graph.Proposition 3.

4:The graph obtained by duplicating a vertex vl in the rim of Snis a prime graph.Proof:Consider a Sunlet graph Sn with 2n vertices.Vertices and Edges of a Sunlet graph is defined by V(Sn)={vp,vp’/p=1,2,…,n} E(Sn)={vpvp’/1?p?n}?{vpvp+1/1?p?n-1}?{v1vn}Let Gl be the graph obtained by duplicating the vertex vl in Sunlet graph Sn and the new vertex vl*.Then |V(Gl)|=2n+1.

Let g:V?{1,2,3,…,2n+1} be a bijective function and Define the label g by, Take gvl=1, gvl’=2, gvl*=3, gvl+1=5,gvl+1’=4 gvp=2p+1 3?p?n gvp’=2p 3?p?nThen for each g admits a prime labeling. Hence G is prime graph.Example 3.

4:Consider the graph S4 v1′ v1 v3′ v3 v2 v2 ‘ v4 v4’ 8 9 6 7 1 2 3 5 4Therefore we seen the above example we get, thus the graph obtained by duplicating a vertex vl in the rim of S4is a prime graph.CHAPTER – IVSOME NEW RESULTS ON PRIME GRAPHS Theorem 4.1:The graph obtained by identifying any two vertices of Pn is a prime graph.

Proof:Take the path Pn vertices are vp for p=1,2,…,n. Let the new vertex be u of the graph G obtained by identifying two distinct vertices vx and vy of path Pn. Then the graph G nothing but a cycle with at the most two paths attached at u.Example 4.1:Now we consider the graph P6.A prime labelling of P6 v1 v2 v3 v4 v5 v6 1 2 3 4 5 6 u 1 2 3 4 5 A prime labelling of the graph obtained by identifying v1 and v2 of P6.

2 1 3 4 5A prime labelling of the graph obtained by identifying v1 and v3 of P6. 3 2 1 4 5A prime labelling of the graph obtained by identifying v1 and v4 of P6. 4 3 1 5 2A prime labelling of the graph obtained by identifying v1 and v5 of P6.

1 5 2 4 4 3 A prime labelling of the graph obtained by identifying v1 and v6 of P6.Therefore the graph obtained by identifying any two vertices of P6 is a prime graph.Theorem 4.

2:Every path is a strongly prime graph.Proof:Take the path Pn vertices are vp for p=1,2,…,n. If vx be any arbitrary vertex of path Pn then the possibilities are as follows:Case(i):If the pendant vertices vx(vx=v1) then the function g:VPn?{1,2,…,n} defined by gvp=p for all p=1,2,…,n, is a prime labeling for path Pnwith gvx=gv1=1.Case(ii):If vx is not a pendant vertex then x=q for some j?2,3,…,n-1 Then g:V?{1,2,3,…,|V|} be a bijective function and Define the label g by, gvp=n+p-q+1 if p=1,2,…,q-1 gvp=p-q+1 if p=q,q+1,…,n Is a prime labeling of path Pn with gvx=gv1=1.Hence from the above cases we get that Pn strongly prime graph.Example 4.2:Consider a path graph P6. v1 v2 v3 v4 v5 v6 1 2 3 4 5 6A prime labelling of P6 having v1 as label 1. 6 1 2 3 4 5 A prime labelling of P6 having v2 as label 1. 5 6 1 2 3 4 A prime labelling of P6 having v3 as label 1. 4 5 6 1 2 3 A prime labelling of P6 having v4 as label 1. 3 4 5 6 1 2 A prime labelling of P6 having v5 as label 1. 2 3 4 5 6 1 A prime labelling of P6 having v6 as label 1.Arbitrary vertex of P6 satisfying the prime labelling g satisfying gv=1.Hence the path graph is strongly prime graph.Theorem 4.3:Every cycle is a strongly prime graph.Proof:Take the cycle Cn vertices are vp for p=1,2,…,n. If v be an arbitrary vertex of cycle Cn. Then v=v1 for some j?2,3,…,n-1 Then g:V?{1,2,3,…,|V|} be a bijective function and Define the label g by,gvp=n+p-q+1 if p=1,2,…,q-1 gvp=p-q+1 if p=q,q+1,…,n Is a prime labeling for cycle Cn with gvx=gv1=1.Hence g admits a prime labeling as well as it is possible to assign label 1 to any arbitrary vertex of cycle Cn, therefore the cycle Cn strongly prime graph.Example 4.3:Consider a Cycle graph C6. v1 1 v6 6 v2 2 v5 5 v4 4 v3 3A prime labelling of C6 having v1 as label 1. 6 5 4 1 2 3A prime labelling of C6 having v2 as label 1. 5 4 6 3 2 1A prime labelling of C6 having v3 as label 1. 4 3 5 2 1 6A prime labelling of C6 having v4 as label 1. 3 2 4 1 6 5A prime labelling of C6 having v5 as label 1. 2 1 4 3 6 5A prime labelling of C6 having v6 as label 1.Arbitrary vertex of C6 satisfying the prime labelling g satisfying gv=1.Hence the Cycle graph is strongly prime graph.Theorem 4.4:The graph obtained by identifying any two vertices of K1,n is a prime graph.Proof:The result is obviously true for n=1,2.So we take n?3. Take the apex vertex v0 and successive pendant vertices vp, for p=1,2,…,n of K1,n.Two vertices of K1,n can be identified in two possible ways are as follows:Case (i):Let v0 be the apex vertex and its identified with any of the pendant vertices(say v1).And the new vertex u0, resultant graph named be G. Then dGvp=1 for p=1,2,…,n and dGu0=n+1 as there is a loop incident at u0.Let g:V(G)?{1,2,3,…,n} be a bijective function as gvp=p for p=1,2,…,n and gu0=1.We know that g is an injection and gcdgu,gv=1 for every pair of adjacent vertices u and v of G. Thus G is a prime graph. Case(ii):Any two of pendant vertices(say vn-1 and vn) are identified. Take the new vertex un-1 be and the resultant graph be G. Then dGvp=1 for p=1,2,…,n and dGun-1=2 and dGv0=nLet g:V(G)?{1,2,3,…,n} be a bijective function as gvp=p+1 for p=0,1,2,…,n-2 and gun-1=n.We know that g is an injection and gcdgu,gv=1 for every pair of adjacent vertices u and v of G. Thus G is a prime graph. Example 4.4:Now we consider the graph K1,8.The prime labelling of the graph obtained by identifying the apex vertex with a pendant vertex of K1,8. 8 2 7 1 3 6 5 4The prime labeling of the graph obtained by identifying the apex vertex with a pendant vertex in K1,8. The prime labeling of the graph obtained by identifying two of the pendant vertex v1 and v8 in K1,8. The labels are defined by the idea of the above theorem, hence we get gv1=1,gv2=2,gv3=3,gv4=4, gv5=5,gv6=6,gv7=7,gv8=8All the vertices of the graph K1,8 are satisfied with the GCD of 1.Therefore the graph K1,8 is a prime graph.