Ratio Mathematica Volume 46, 2023 Some new odd prime graphs S. Meena* G. Gajalakshmi† Abstract For a graph G, a bijection f is called an odd prime labeling , if f from V to {1, 3, 5, ...., 2|V |−1} for each edge uv in G the greatest common divisor of the labels of end vertices (f(u), f(v)) is one. In this paper we investigate the existence of odd prime labeling of some new classes of graphs and we prove that the graphs such as the Z−Pn graph, Fish graph, Umbrella graph, Cocount tree , F -tree, Y -tree and Double Sunflower graph are odd prime graphs. Keywords: Odd prime graph, Z − Pn graph, Fish graph, Umbrella graph,Cocount tree , F -tree, Y -tree, Double Sunflower graph. 2020 AMS subject classifications: 05C78 1 *Department Of Mathematics, Govt, Arts & Science College, Chidambaram 608 102, India; meenasaravanan14@gmail.com. †Department Of Mathematics, Govt, Arts & Science College, Chidambaram; gaja61904@gmail.com. 1Received on September 15, 2022. Accepted on December 15, 2022. Published on March 20, 2023. DOI: 10.23755/rm.v46i0.1056. ISSN: 1592-7415. eISSN: 2282-8214. ©S. Meena et al. This paper is published under the CC-BY licence agreement. 44 S. Meena and G. Gajalakshmi 1 Introduction In this paper by a graph G = 〈V (G), E(G)〉 we mean a simple graph. For graph theoretical terminologies we refer J .A.Bondy and U .S. R.Murthy [1976]. A graph labeling is an assignment of integers to the vertices or edges or both subject to some constraints. For entire survey of graph labeling we refer Gallian [2009]. The concept of prime labeling was introduced by Roger Etringer and was studied further by many researchers Deretsky et al. [1991], Tout et al. [1982].Meena and Vaithilingam [2013] proved that crown related graphs are prime graphs. Meena and Naveen [2018] investigated about the prime labeling of graphs related to bicyclic graphs. Prime labeling in the concept of graph operation was discussed by Meena and Kavitha [2015]. The Existence of odd prime labeling for some new classes of graph was discussed by Meena et al. [2021]. The notion of odd prime labeling was introduced by Prajapati and Shah [2018] and they have proved many researchers. We give some families of odd prime graphs and some necessary condition for a graph to be odd prime graph. Motivated by this study, further studied by in this paper we investigate the existence of odd prime labeling of some new classes of odd prime graphs. Definition 1.1. Let G = 〈V (G), E(G)〉 be a graph. A bijection f : V (G) → O|V | is called an odd prime labeling if for each edge uv ∈ E, greatest common divisor 〈f(u), f(v)〉is1. A graph is called an odd prime graph if its admits odd prime labeling. Here O|V | = {1, 3, 5, ...2|V |−n} Definition 1.2. Z − Pn is a graph obtained from a pair of P1 and P2 of path of length n in which the ith vertex of a path P1 is joined with (i + 1)th vertex of a path P2. Definition 1.3. Fish graph is a graph obtained by attaching one of the vertex of K3 to any one of the vertex of Cn.It is denoted by Cn@K3. Definition 1.4. For any integers m > 2, n > 1.An umbrella graph U(m, n) is the graph obtained by identifying the end vertex of path Pn with the central vertex of a Fan graph Fm. Definition 1.5. Coconut tree graph is obtained by identifying the central vertex of K1,m with a pendant vertex of the path Pn. Definition 1.6. F - tree on n + 2 vertices, denoted by Fn is obtained from a path Pn by attaching exactly two pendant vertices of the n−1 and nth vertex of Pn. 45 Some new odd prime graphs Definition 1.7. Y - tree on n + 1 vertices, denoted by Yn is obtained from a path Pn by attaching a pendant vertex of the nth vertex of Pn. Definition 1.8. A double sunflower graph order n, denoted by DSFn, is a graph obtained from the graph SFn by intserting a new vertex Ci on each edges aiai+1 and adding edges for each i. 2 Main results Theorem 2.1. Z − (Pn) is an odd prime graph for all integers n ≥ 3. Proof. Let G = Z − (Pn) be the graph V (G) = {ui, vi/1 ≤ i ≤ n} E(G) = {(uiui+1), (vivi+1)/1 ≤ i ≤ n−1}∪{(viui+1)/1 ≤ i ≤ n−1} Now |V (G)| = 2n and |E(G)| = 3(n-1) Define a labeling f : V → O2n as follows f(ui) = 4i-5 for 1 ≤ i ≤ n f(vi) = 4i+1 for 1 ≤ i ≤ n Clearly vertex labels are distinct. For each e = uv ∈ E, if gcd(f(u), f(v)) = 1 (i) e = u1u2, gcd(f(u1), f(u2)) = gcd(1, 3) = 1 (ii) e = uiui+1, gcd(f(ui), f(ui+1)) = gcd(4i−5, 4i−1) = 1 for 1 ≤ i ≤ n (iii)e = vivi+1, gcd(f(vi), f(vi+1)) = gcd(4i + 1, 4i + 5) = 1 for 1 ≤ i ≤ n (iv) e = viui+1, gcd(f(vi), f(ui+1)) = gcd(4i + 1, 4i−5) = 1 for 1 ≤ i ≤ n (v) e = vn−1vn, gcd(f(vn−1)), f(vn) = gcd(4n−3, 4n−1) = 1 for 1 ≤ i ≤ n Thus f admits odd prime labeling on Z − (Pn) and hence Z − (Pn) is an odd prime graph. Figure 1: Z − (Pn) and its odd prime labeling Theorem 2.2. Fish graph is an odd prime graph for n ≥ 3. Proof. Let G = Cn@K3 be the graph V (G) = {ui/1 ≤ i ≤ n}∪{(v1v2)} E(G) = {(uiui+1)/1 ≤ i ≤ n−1}∪{(u1un)}∪{u1vi/1 ≤ i ≤ 2} ∪ {(v1, v2)} 46 S. Meena and G. Gajalakshmi Now |V (G)|= n + 2 and |E(G)| = n + 3 Define a labeling f : V → On+2 as follows. f(u1) = 1 f(v1) = 3 f(v2) = 5 f(ui) = 2i + 3 for 2 ≤ i ≤ n Clearly vertex labels are distinct. For each e = uv ∈ E, if gcd(f(u), f(v)) = 1 (i) e = v1v2, gcd(f(v1), f(v2)) = gcd(3, 5) = 1 (ii) e = u1v1, gcd(f(u1), f(v1)) = gcd(1, 3) = 1 for 1 ≤ i ≤ n (iii)e = u1v2, gcd(f(u1), f(v2)) = gcd(1, 5) = 1 for 1 ≤ i ≤ n (iv) e = uiui+1, gcd(f(ui), f(ui+1) = gcd(2i + 3, 2i + 5) = 1 for 2 ≤ i ≤ n−1 (v) e = u1u2, gcd(f(u1), f(u2) = gcd(1, f(u2) = 1 (vi) e = u1un, gcd(f(u1), f(un) = gcd(1, f(un) = 1 Thus f admits odd prime labeling on Cn@K3 and hence Fish graph is an odd prime graph. Figure 2: Fish graph Cn@K3 and its odd prime labeling Theorem 2.3. The Umbrella graph U(m, n) is an odd prime graph. Proof. Consider the umbrella graph U(m, n) with vertex set. V (U(m, n)) = {xi, yi/1 ≤ i ≤ m, 1 ≤ i ≤ n} E(U(m, n)) = {xixi+1/1 ≤ i ≤ m−1} ∪{xiy1/1 ≤ i ≤ m}∪{yiyi+1/1 ≤ i ≤ n−1} Now |V (U(m, n))| = m + n and |E(U(m, n))| = 2m + n−2 Define f : V → Om+n as follows. f(xi) = 2i + 1 for 1 ≤ i ≤ m f(y1) = 1 f(yi) = 2(i + m)−1 for 2 ≤ i ≤ n Clearly vertex labels are distinct. With this labeling for each e = uv ∈ E, if gcd(f(u), f(v)) = 1. 47 Some new odd prime graphs (i) e = xixi+1, gcd(f(xi), f(xi+1)) = gcd(2i+1, 2i+3) = 1 for 1 ≤ i ≤ m−1 (ii) e = xiy1, gcd(f(xi), f(y1)) = gcd(2i + 1, 1) = 1 for 1 ≤ i ≤ m (iii)e = y1y2, gcd(f(y1), f(y2)) = gcd(1, 2m + 3) = 1 (iv) e = yiyi+1, gcd(f(yi), f(yi+1) = gcd(2(i + m) − 1, 2(i + m) + 1) = 1 for 2 ≤ i ≤ n−1 as they are consecutive odd integers. This f is a odd prime labeling on U(m, n) and hence it is an odd prime graph. Figure 3: U(m, n) and its odd prime labeling Theorem 2.4. Cocount tree CT(m, n) is an odd prime graph. Proof. V (G) = {ui, vi/1 ≤ i ≤ m, 1 ≤ i ≤ n} and edge set E(G) = {uiv1/1 ≤ i ≤ m}∪{vivi+1/1 ≤ i ≤ n−1} Now |V (CT(m, n))| = m + n and |E(CT(m, n))| = m + n−1 Define a labeling f : V (G) →{1, 3, 5, ....2m + 2n−1} as follows f(ui) = 2(n + i)−1 for 1 ≤ i ≤ m f(vi) = 2i−1 for 1 ≤ i ≤ n Clearly vertex labels are distinct. For each e = uv ∈ E, if gcd(f(u), f(v)) = 1 (i) e = uiv1, gcd(f(ui), f(v1)) = gcd(2(n + 1)−1, 1) = 1 for 1 ≤ i ≤ n; (ii) e = vivi+1, gcd(f(vi), f(vi+1)) = gcd(2i−1, 2i + 1)=1 for 1 ≤ j ≤ m−1. Thus f admits odd prime labeling on CT(m, n) and hence CT(m, n) is an odd prime graph. 48 S. Meena and G. Gajalakshmi Figure 4: CT(m, n) and its odd prime labeling Theorem 2.5. Let G be the graph obtained by identifying a pendant vertex of Pm with a leaf of K1,n then G is an odd prime graph for all m and n. Proof. V (G) ={u, ui, vj/1 ≤ i ≤ n, 2 ≤ i ≤ m} and the edge set E(G) = {uvi/1 ≤ i ≤ n}∪{vjvj+1/2 ≤ j ≤ m−1}∪{uv2} Here u = v1 Now |V (G)| =m+n and |E(G)| = m + n−1 Define a labeling f : V (G) →{1, 3, 5, ....2m + 2n−1} as follows f(u) = 1 f(ui) = 2i + 1 for 1 ≤ i ≤ n f(vi) = 2(n + i)−1 for 2 ≤ i ≤ n Clearly the vertex labels are distinct. For each e = uv ∈ E if gcd(f(u), f(v)) = 1 (i) e = uui, gcd(f(u), f(ui)) = gcd(1, 2i + 1) = 1 for 1 ≤ i ≤ n; (ii) e = uv2, gcd(f(u), f(v2)) = gcd(1, 2n + 3) = 1 for 1 ≤ i ≤ n; (iii)e = vivi+1, gcd(f(vi), f(vi+1))= gcd(2(n + i) − 1, 2(i + n) + 1) =1 for 2 ≤ i ≤ n; Thus f admits odd prime labeling on G and hence G is an odd prime graph. 49 Some new odd prime graphs Figure 5: G and its odd prime labeling Theorem 2.6. F - tree FPn n ≥ 3 is an odd prime graph. Proof. Let V (G) = {u, v, vi, /1 ≤ i ≤ n−1} E(G) = {vivi+1/1 ≤ i ≤ n−1}∪{uv2, vv1} be the vertex set and edge set of FPn Now |V (FPn)| = n + 2 and |E(FPn)| = n + 1 Define a labeling f : V (G) →{1, 3, 5, ....2n + 3} as follows f(u) = 3 f(v) = 1 f(vi) = 2i+3 for 1 ≤ i ≤ n Clearly vertex labels are distinct. For each e = uv ∈ E if gcd(f(u), f(v)) = 1 (i) e = vv1, gcd(f(v), f(v1)) = gcd(1, 5) = 1 (ii)e = uv2, gcd(f(u), f(v2)) = gcd(3, 7) = 1 (iii)e = vivi+1, gcd(f(vi), f(vi+1)) = gcd(2i + 3, 2i + 5) = 1 Thus f admits odd prime labeling on FPn and hence F - tree FPn is an odd prime graph. Figure 6: FPn and its odd prime labeling Theorem 2.7. Y - tree is an odd prime graph. Proof. Let V (G) = {uvi, /1 ≤ i ≤ n} E(G) = {vivi+1, vn−1u /1 ≤ i ≤ n−1} be the vertex set and edge set of y-tree Now |V (G)| = n + 1 and |E(G)| = n 50 S. Meena and G. Gajalakshmi Define a labeling f : V (G) →{1, 3, 5, ....2n + 1} as follows f(u) = 2n+1 f(vi) = 2i-1 for 1 ≤ i ≤ n Clearly vertex labels are distinct. For each e = uv ∈ E if gcd(f(u), f(v)) = 1 (i) e = uvn−1, gcd(f(u), f(vn−1)) = gcd(2n + 1, 2n−1) = 1 (iii) e = vivi+1, gcd(f(vi), f(vi+1)) = gcd(2i−1, , 2i + 1) = 1 for 1 ≤ i ≤ n−1 Thus f admits odd prime labeling on Y -tree and hence Y - tree is an odd prime graph. Figure 7: Y -tree and its odd prime labeling Theorem 2.8. For any natural numbers k ≥ 3 graph DSFn is an odd prime graph. Proof. The vertex set and edge set of DSFn of order K respectively are V (DSFn) = {li, mi, ni/1 ≤ i ≤ k} E(DSFn) = {limi, lini, mini, mili+1, lkmk, lknn, l1nk/1 ≤ i ≤ n−1} Now |V (DSFn)| = 3k and |E(DSFn)| = 5k Define a labeling f : V (DSFn) →{1, 3, 5, ....6n−1} as follows f(li) = 6i−5 for 1 ≤ i ≤ n f(mi) = 6i−3 for 1 ≤ i ≤ n f(ni) = 6i−1 for 1 ≤ i ≤ n Clearly all the vertex labels are distinct. With this labeling for each e = uv ∈ E if gcd(f(u), f(v)) = 1 (i) e = limi, gcd(f(li), f(mi)) = gcd(6i−5, 6i−3) = 1 for 1 ≤ i ≤ n (ii) e = lini, gcd(f(li), f(ni)) = gcd(6i−5, 6i−1) = 1 for 1 ≤ i ≤ n (iii) e = mini, gcd(f(mi), f(ni) = gcd(6i−3, 6i−1) = 1 for 1 ≤ i ≤ n (iv) e = mili+1, gcd(f(mi), f(li+1)) = gcd(6i−3, 6i−5) = 1 for 1 ≤ i ≤ n−1 (v) e = mkl1, gcd(f(mk), f(l1)) = gcd(f(mk), f(l1)) = 1 Thus f is a odd prime labeling on DSFn and hence DSFn is an odd prime graph. 51 Some new odd prime graphs Figure 8: DSFn and its odd prime labeling 3 Conclusions Odd Prime labelings of various classes of graphs such as Z − Pn graph, Fish graph, Umbrella graph, Cocount tree, F -tree, Y -tree and Double Sunflower graph are investigated. To derive similar results for other graph families is an open area of research. References T. Deretsky, S. Lee, and J. Mitchem. On vertex prime labelings of graphs, in graph theory, combinatorics and applications, j. alavi, g. chartrand, o. oeller- man, and a. schwenk, eds.,. Proceedings 6th International Conference Theory and Applications of Graphs (Wiley, New York),, 1:359 – 369, 1991. J. Gallian. A dynamic survey of graph labeling. DS6, 2009. J .A.Bondy and U .S. R.Murthy. Graph Theory and Applications. (North- Holland), New York, 1976. 52 S. Meena and G. Gajalakshmi S. Meena and P. Kavitha. Prime labeling of duplication of some star related graphs. International Journal of Mathematics Trends and Technology, 23:26 – 32, 2015. S. Meena and J. Naveen. On prime vertex labeling of corona product of bicyclic graphs. Journal of Computer and Mathematical Sciences, 9:1512 – 1526, 2018. S. Meena and K. Vaithilingam. Prime labeling for some crown related graphs. International Journal of Scientific & Technology Research, 2:92 – 95, 2013. S. Meena, P. Kavitha, and G. Gajalakshmi. Prime labeling of h super subdivision of cycle related graph. AIP Conference Proceedings (communicated). S. Meena, G. Gajalakshmi, and P. Kavitha. Odd prime labeling for some new classes of graph (communicated). SEAJM, 2021. U. Prajapati and K. Shah. On odd prime labeling. International journal of Re- search and Analytical Reviews, 5:284 – 294, 2018. A. Tout, A. Dabboucy, and K. Howalla. Prime labeling of graphs. Nat. Acad. Sci letters, 11:365 – 368, 1982. 53