EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 17, No. 4, 2024, 3557-3566 ISSN 1307-5543 – ejpam.com Published by New York Business Global Prime Labeling of Union of Some Graphs Omar A. Abughneim1,∗, Baha’ Abughazaleh2 1 Department of Mathematics, Faculty of Sciences, The University of Jordan, Amman, Jordan 2 Department of Mathematics, Faculty of Sciences, Isra University, Amman, Jordan Abstract. A prime labeling of a graph G is a map from the vertex set of G, V (G), to the set {1, 2, ..., |V (G)|} such that any two adjacent vertices in the graph G have labels that are relatively prime. In this paper, we discuss when the disjoint union of some graphs is a prime graph. 2020 Mathematics Subject Classifications: 05C78 Key Words and Phrases: Independence number, Even cycles, Wheels, Prime labeling, Prime graphs, Maximal prime graphs 1. Introduction A path Pm in a graph is an alternative sequence of vertices and edges with no repeated vertices, a cycle Cm in a graph is a path that begins and ends at the same vertex and a wheel graph Wm is formed by joining a single vertex, known as the apex vertex, to all vertices of a cycle Cm, these vertices are known as the rim vertices. A bijective map f from the vertex set of a graph G to {1, 2, ..., |V (G)|} such that f (u) and f (v) are relatively prime whenever u and v are adjacent in G is called a prime labeling (PL) of G and a graph G is called a prime graph (PG) if G has a PL. Entringer defined the PL that was introduced by Tout et. al. in [1]. Entringer conjectured that all trees could be prime labeled, a hypothesis supported by Haxell et. al. in [8] proving that all sufficiently large trees have this property. Seoud et. al. in [7] further contributed by providing necessary and sufficient conditions for a graph to admit a prime labeling. For more details about prime graphs see for example [2], [5], [6], [10]. In this paper, we discuss when the disjoint union of some graphs is a PG. We prove that Wm∪Pn is a PG if and only if m is even or n is odd. Also, we show that C2n∪C2n∪W2m and C2n ∪ C2n ∪ C2n ∪ W2m are PGs. Finally, we study some properties of the disjoint union between a complete graph and any graph such that this union is a PG. Readers are advised to refer to the appropriate references or sources for clarification on terms and concepts that have not been defined in the text in [3] and [4]. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v17i4.5336 Email addresses: o.abughneim@ju.edu.jo (O.A. Abughneim), baha.abughazaleh@iu.edu.jo (B. Abughazaleh) https://www.ejpam.com 3557 Copyright: © 2024 The Author(s). (CC BY-NC 4.0) O. A. Abughneim, B. Abughazaleh / Eur. J. Pure Appl. Math, 17 (4) (2024), 3557-3566 3558 2. Prime labeling of union of some graphs In this section, we generalize a result in [11], we prove that Wm∪Pn is a PG if and only if m is even or n is odd. Also, we show that C2n ∪C2n ∪W2m and C2n ∪C2n ∪C2n ∪W2m are PGs. The following lemma imposes certain restrictions on the independence number of PGs. Lemma 1. [14] “For any PG G, we have α(G) ≥ [ |V (G)| 2 ] .” The authors in [11] proved that “the disjoint union of a PG of even order and a graph of order 3 is a PG.” In the following theorem, we generalize this result. Theorem 1. Let G1 and G2 be PGs of orders n and m respectively. If for any prime p ≤ m− 1, we get p divides n, then G1 ∪G2 is a PG. Proof. Let u1, u2, ..., un be the vertices of G1, v1, v2, ...vm be the vertices of G2, f : V (G1) −→ {1, 2, ..., n} be a PL of G1 and g : V (G2) −→ {1, 2, ...,m} be a PL of G2. Define h : V (G1 ∪G2) −→ {1, 2, ..., n+m} by h (ui) = f (ui) for all 1 ≤ i ≤ n, and h(vj) = n+ g(vj) for all 1 ≤ j ≤ m. If ui and uj are adjacent in G1. Then (h (ui) , h (uj)) = (f (ui) , f (uj)) = 1 because f is a PL. Suppose vi and vj are adjacent in G2 and d = (h (vi) , h (vj)) = (n+ g (ui) , n+ g (uj)) . Thus d divides g (ui) − g (uj) and |g (ui)− g (uj)| ≤ m − 1. If d > 1, then d has a prime divisor say p. Therefore, p ≤ d ≤ m − 1 and by assumption p divides n. But p divides n + g (ui) and p divides n + g (uj). Thus p divides g (ui) and p divides g (uj) and hence (g (ui) , g (uj)) ≥ p which is a contradiction, because g is a PL. Therefore, (h (vi) , h (vj)) = 1 and so h is a PL of G1 ∪G2. Vaidya et. al. in [13] proved the following theorem Theorem 2. [13] “W2k ∪ Pm is a PG.” Next, we show when, in general, Wm ∪ Pn is a PG. Theorem 3. Wm ∪ Pn is a PG if and only if m is even or n is odd. Proof. We separate the proof in the following cases, (i) Suppose m is odd and n is even. Let m = 2k + 1 and n = 2h. Then α(Wm∪Pn) = α(Wm)+α (Pn) = k+h < [ |Wm ∪ Pn| 2 ] = [ 2k + 2 + 2h 2 ] = k+h+1. By Lemma 1, we get Wm ∪ Pn is not a PG. O. A. Abughneim, B. Abughazaleh / Eur. J. Pure Appl. Math, 17 (4) (2024), 3557-3566 3559 (ii) Suppose m is even. By Theorem 2, Wm ∪ Pn is a PG. (iii) Suppose m and n are odd. Let u0 be the apex vertex of Wm, u1, u2, ..., um be the consecutive rim vertices of Wm and v1v2...vn be the path Pn and define f : V (Wm ∪ Pn) −→ {1, 2, ...,m+ n+ 1} as follows: f(ui) = { i+ 1 , 0 ≤ i ≤ 2 i+ 2 , 3 ≤ i ≤ m and f(vj) = { m+ j + 2 , 1 ≤ j ≤ n− 1 4 , j = n . Since f(u0) = 1, f(u0) is relatively prime to f(ui) for all 1 ≤ i ≤ m. Also, (f(u2), f(u3)) = (3, 5) = 1, (f(u1), f(um)) = (2, n+ 2) = 1, because m is odd. Now, (f(vn−1), f(vn)) = (m+ n+ 1, 4) = 1, because m+ n+ 1 is odd. The labels assigned to adjacent vertices within the graph Wm∪Pn exhibit a property of being mutually prime because these labels are two consecutive integers. So f is a PL. Theorem 4. The disjoint union of two wheels is not a PG. Proof. Let Wn and Wm be any two wheels. Then α(Wn ∪Wm) = α(Wn) + α (Wm) = [n 2 ] + [m 2 ] ≤ [ n+m 2 ] < [ |Wn ∪Wm| 2 ] = [ n+m+ 2 2 ] = [ n+m 2 ] + 1. By Lemma 1, we get Wn ∪Wm is not a PG. Patel et. al. in [9] proved that “the disjoint union of an even wheel and an even cycle is a PG.” In Theorem 5, we prove that C2n ∪ C2n ∪W2m and C2n ∪ C2n ∪ C2n ∪W2m are PGs. Theorem 5. C2n ∪ C2n ∪W2m and C2n ∪ C2n ∪ C2n ∪W2m are PGs for all n,m. Proof. Let u1, u2, ..., u2n be the vertices of the first cycle, u2n+1, u2n+2, ..., u4n be the vertices of the second cycle, u4n+1, u4n+2, ..., u6n be the vertices of the third cycle, v0 be the apex vertex of Wn and v1, v2, ..., v2m be the consecutive rim vertices of W2m. (i) To show that C2n ∪ C2n ∪W2m is a PG. We have the following two cases: (a) i. If 3 does not divide n+ 1, define f : V (C2n ∪ C2n ∪W2m) −→ {1, 2, ..., 4n+ 2m+ 1} as follows: f (ui) = i+ 2, for all 1 ≤ i ≤ 4n, O. A. Abughneim, B. Abughazaleh / Eur. J. Pure Appl. Math, 17 (4) (2024), 3557-3566 3560 f (vj) = j + 1 for j = 0 and 1, f (vj) = 4n+ j + 1, for all 2 ≤ j ≤ 2m. We get (f(u1), f(u2n)) = (3, 2n+ 2) = 1, because 3 does not divide n+ 1. Also, (f(u2n+1), f(u4n)) = (2n+ 3, 4n+ 2) = 1 because if d = (f(u2n+1), f(u4n)), then d divids 2n+3 and hence d is odd and d divids 2(2n+3)−(4n+2) = 4. Thus d = 1. Clearly, any other adjacent vertices have relatively prime la- bels. So, f is a PL. ii. If 3 divides n+ 1, define f : V (C2n ∪ C2n ∪W2m) −→ {1, 2, ..., 4n+ 2m+ 1} as follows: f (ui) = i+ 3, for all 1 ≤ i ≤ 4n− 1, f (u4n) = 3, f (vj) = j + 1 for j = 0 and 1, f (vj) = 4n+ j + 1, for all 2 ≤ j ≤ 2m. Since 3 divides n+1, 3 does not divide 2n+4 and 4n+2. So, (f(u2n+1), f(u4n)) = (2n+ 4, 3) = 1 and (f(u4n−1), f(u4n)) = (4n+ 2, 3) = 1. It is clear that all other adjacent vertices have relatively prime labels. Therefore, f is a PL. (ii) To show that C2n ∪ C2n ∪ C2n ∪W2m is a PG. We have the following two cases: (a) If 3 does not divide 4n+ 1, define f : V (C2n ∪ C2n ∪ C2n ∪W2m) −→ {1, 2, ..., 6n+ 2m+ 1} as follows f (ui) = 6n+ i for i = 1, 2, f (ui) = i for all 3 ≤ i ≤ 6n, f (vj) = j + 1 for j = 0 and 1, f (vj) = 6n+ j + 1 for all 2 ≤ j ≤ 2m. We have (f(u2), f(u3)) = (6n+ 2, 3) = 1, because 3 does not divide 6n+ 2, (f(u1), f(u2n)) = (6n+ 1, 2n) = 1, because 1 = (6n+ 1)− 3 (2n) and (f(u2n+1), f(u4n)) = (2n+ 1, 4n) = 1, because 2 = 2(2n+ 1)− 4n and 2 does not divide 2n+ 1. Also, (f(u4n+1), f(u6n)) = (4n+ 1, 6n) = 1, because 3 = 3(4n+ 1)− 2 (6n) and 3 does not divide 4n+ 1. Thus f is a PL. O. A. Abughneim, B. Abughazaleh / Eur. J. Pure Appl. Math, 17 (4) (2024), 3557-3566 3561 (b) If 3 divides 4n+ 1, define f : V (C2n ∪ C2n ∪ C2n ∪W2m) −→ {1, 2, ..., 6n+ 2m+ 1} as follows f (ui) = 6n+ i for i = 1 and 2, f (u2n) = 4n, f (u4n) = 6n, f (u6n) = 2n, f (ui) = i for all i ̸= 1, 2, 2n, 4n and 6n, f (vj) = j + 1 for j = 0 and 1, f (vj) = 6n+ j + 1 for all 2 ≤ j ≤ 2m. Then, (f(u1), f(u2n)) = (6n+ 1, 4n) = 1, because 2 = 2(6n+ 1)− 3 (4n) and 6n+ 1 is odd, (f(u2n−1), f(u2n)) = (2n− 1, 4n) = (2n− 1, 2n) = 1, (f(u2), f(u3)) = (6n+ 2, 3) = 1, because 3 does not divide 6n+ 2. (f(u4n+1), f(u6n)) = (4n+ 1, 2n) = 1, because 1 = (4n+ 1)− 2(2n). (f(u6n−1), f(u6n)) = (6n− 1, 2n) = 1, because 1 = 3 (2n)− (6n− 1). Now, since 1 = 2(2n + 1) − (4n + 1) and 3 divides 4n + 1, 3 does not divide 2n+ 1. Therefore, (f(u2n+1), f(u4n)) = (2n+ 1, 6n) = (2n+ 1, 2n) = 1. Also, 3 does not divide 4n− 1 because 3 divides 4n+ 1. Thus (f(u4n−1), f(u4n)) = (4n− 1, 6n) = (4n− 1, 2n) = 1. Therefore f is a PL. O. A. Abughneim, B. Abughazaleh / Eur. J. Pure Appl. Math, 17 (4) (2024), 3557-3566 3562 3. prime labeling of union of complete graphs and graphs with maximal size In this section, we will study some properties of the disjoint union between a complete graph and any graph such that this union is a PG. Seoud et. al. in [12] define a maximal PG as follows: Definition 1. [12] “A maximal PG is a PG of n vertices such that adding any new edge yields a non-PG. Usually this graph is denoted by R(n).” Theorem 6. [14] “The largest complete subgraph in the maximal PG of n vertices is of order π(n) + 1, where π(n) is the number of primes less than or equal to n.” Remark 1. Let H be the largest complete subgraph in the maximal PG of n vertices. Then we can label the vertices of H by the primes less than or equal to n together with 1 namely, 1, p1, p2, ...., pπ(n). Also, we can replace the label pi by pki for some k ≥ 2 and pki ≤ n because for any a ∈ Z+, (a, pi) = 1 if and only if ( a, pki ) = 1. Theorem 7. Suppose Kn is the complete graph of order n and Gm is any graph of order m such that Kn ∪Gm is a PG. Then (i) π (n+m) ≥ n− 1. (ii) α (Gm) ≥ [ n+m 2 ] − 1. Proof. (i) By Theorem 6, n = |V (Kn)| ≤ π (n+m) + 1. So, π (n+m) ≥ n− 1. (ii) Since at most one of the vertices of Kn has even label, the set S = {u ∈ V (Gm) : the label of u is even} is an independent set of Gm with cardinality at least [ n+m 2 ] − 1. So, α(Gm) ≥ [ n+m 2 ] − 1. Let Gm be a graph with maximum size such that Kn ∪Gm be a PG. We will examine when Gm is connected. Firstly, we need the following lemma and corollary. Lemma 2. [4]“(Bonse’s inequality) Let k ≥ 5 and p1, p2, ..., pk be the first k primes. Then p2k+1 < k∏ i=1 pi where pk+1 is the prime next to pk.” Also, if k = 4, then pk = 7 and pk+1 = 11 and its clear 112 < (2)(3)(5)(7). So, we have the following corollary. Corollary 1. Let k ≥ 4 and p1, p2, ..., pk be the first k primes. Then p2k+1 < k∏ i=1 pi where pk+1 is the prime next to pk. O. A. Abughneim, B. Abughazaleh / Eur. J. Pure Appl. Math, 17 (4) (2024), 3557-3566 3563 Theorem 8. Let Gm be a graph with maximum size such that Kn ∪ Gm be a PG and π (n+m) ≥ n. Then Gm is connected. Proof. Since π (n+m) ≥ n, then the number of primes less than or equal to n + m is greater than or equal to the number of vertices of Kn and these primes are mutually relatively prime. So, we can use a subset of these primes to label the vertices of Kn and hence one of the vertices of Gm will be labeled by 1. This vertex is adjacent to all other vertices of Gm, because Gm is a graph with maximum size such that Kn ∪ Gm is a PG. Thus, Gm is connected. Theorem 9. Let Gm be a graph with maximum size such that Kn ∪ Gm be a PG and π (n+m) = n− 1. Then (i) Gm is the trivial graph (m = 1) whenever n+m = 4 or 5. (ii) Gm is disconnected whenever 6 ≤ n+m < 25 or 30 ≤ n+m < 49. (iii) Gm is connected whenever 25 ≤ n+m < 30 or n+m ≥ 49. Proof. By Remark 1, label the vertices of Kn by the primes less than or equal to n+m together with 1 and label the vertices of Gm by the composite numbers less than or equal to n+m. (i) If n+m = 4, then π (n+m) = 2. So n = π (n+m)+1 = 3. Thus m = 1. Similarly, if n+m = 5. (ii) If 6 ≤ n+m < 25, then the vertex of Gm whose label is 6 must be an isolated vertex in Gm because any composite number less than 25 is not relatively prime to 6. Thus Gm is disconnected. If 30 ≤ n+m < 49, then any composite number less than 49 is not relatively prime to 30 So, 30 is isolated and thus Gm is disconnected. (iii) Let p1, p2, ..., pk be the primes less than or equal √ n in ascending order. We refer to the vertices of Gm by their labels. We partition the vertices of Gm into the following sets A0 = {p21, p22, ..., p2k} and Ai = {s : pi does not divide s} − j=i−1⋃ j=0 Aj for all i = 1, 2, ...k. Notice that A0, A1, A2, ..., Ak are mutually disjoint sets. We want to show that Gm = i=k⋃ i=0 Ai. Suppose there is a composite number t less than or equal to n+m such that pi divides t for all i = 1, 2, ...k. If 25 ≤ n+m < 30, then 2 divides t, 3 divides t and 5 divides t. So, t ≥ 30 which is a contradiction. If n+m ≥ 49, then by Corollary 1 we O. A. Abughneim, B. Abughazaleh / Eur. J. Pure Appl. Math, 17 (4) (2024), 3557-3566 3564 get p2k+1 < k∏ i=1 pi where pk+1 is the prime next to pk. So, n+m < p2k+1 < k∏ i=1 pi < t because pi divides t for all i = 1, 2, ..., k which is a contradiction. Now, Let u, v ∈ Gm. We want to find a path between u and v and this shows that Gm is connected. We have the following cases: (a) If u, v ∈ A0, then u− v is a path in Gm. (b) If u, v ∈ Ai for some i = 1, 2, ...k, then u− p2i − v is a path in Gm. (c) If u ∈ Ai for some i = 1, 2, ...k and v ∈ Aj for some j = 1, 2, ...k such that i ̸= j, then u− p2i − p2j − v is a path in Gm. (d) If u ∈ A0 and v ∈ Aj for some j = 1, 2, ...k, then u − p2j − v is a path in Gm whenever u ̸= p2j and u− v is a path in Gmwhenever u = p2j . Therefore, Gm is connected. Example 1. (i) Consider the complete graph K5 and let G4 be a graph with maximum size such that K5 ∪G4 is a PG. Then, π(9) = 4 = 5− 1 and since K5 ∪G4 is a PG, we can label the vertices of K5 by the numbers 1, 2, 3, 5, 7 and hence G4 is the following graph 4 86 9 G4 So, G4 is disconnected. (ii) Consider the complete graph K10 and let G15 be a graph with maximum size such that K10 ∪G15 is a PG. Then, π(25) = 9 = 10− 1 and since K10 ∪G15 is a PG, we can label the vertices of K10 by the numbers 1, 2, 3, 5, 7, 11, 13, 17, 19, 23 and hence G15 is the following graph REFERENCES 3565 6 4 8 22 10 12 25 15 2018 16 21 9 24 14 G15 So, G15 is connected. References [1] AN Dabboucy A Tout and K Howalla. Prime labeling of graphs. Nat. Acad. Sci. Lett., 11:365–368, 1982. [2] B Abughazaleh and OA Abughneim. Prime labeling of graphs constructed from wheel graph. Heliyon, 10(2):e23979, 2024. [3] G Agnarsson and R Greenlaw. Graph Theory: Modeling, Applications, and Algo- rithms, 1st ed.. Pearson Education, Ann Arbor, Michigan, 2007. [4] David M. Burton. Elementary Number Theory. Tata McGraw Hill Education, New York, 7th edition, 2009. [5] HL Fu and KC Huang. On prime labellings. Discrete Math, 127:181–186, 1994. [6] JA Gallian. A dynamic survey of graph labeling. Electron. J. Comb., 6(25):4–623, 2022. [7] A el Sonbaty MA Seoud and AEA Mahran. On prime graphs. Ars Comb., 104:241– 260, 2012. [8] O Pikhurko P Haxell and A Taraz. Primality of trees. J. Combinatorics, 2:481–500, 2011. [9] SK Patel and JB Vasava. On prime labeling of some union graphs and circulant graphs. Inter. J. Sci. Res. Math. Stat. Sci., 5(6):248–254, 2018. [10] O Pikhurko. Trees are almost prime. Discrete Math, 307:1455–1462, 2007. [11] UM Prajapati and SJ Gajjar. Some results on prime labeling. Open J. Discrete Math, 4:60–66, 2014. [12] MA Seoud and MZ Youssef. On prime labelings of graphs. Congr. Numer., 141:203– 215, 1999. REFERENCES 3566 [13] SK Vaidya and UM Prajapati. Some results on prime and k-prime labeling. J. Math. Res., 3(1):248–254, 2011. [14] MZ Youssef. On Graceful, Harmonious and Prime Labelings of graphs. PhD thesis, Department of Mathematics, Ain Shams University, 2000.