Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 42 https://internationalpubls.com On Edge Prime Index of a Graph Janani R1*, Ramachandran T2 1* Department of Mathematics, SSM Institute of Engineering and Technology, Dindigul, Tamilnadu, India. 2 Department of Mathematics, MVM Government Arts College (W), Dindigul, Tamilnadu, India. *Corresponding author(s). E-mail(s): raseja3@gmail.com; Contributing authors: yasrams@gmail.com; Article History: Received: 20-01-2024 Revised: 30-03-2024 Accepted: 24-04-2024 Abstract: Relatively Prime Edge labeling extends the notion of prime labeling by considering edges. Prime labeling requires adjacent vertices to possess relatively prime labels, while relatively prime edge labeling requires adjacent edges to have relatively prime labels. The transformation of a coprime edge-labeled graph into a relatively prime edge-labeled graph introduces the concept of Edge Prime Index (or Relatively Prime Index). This study focuses on cases where a coprime edge-labeled graph can be converted into a relatively prime edge-labeled graph by removing certain edges from graph G, thereby establishing the concept of Edge Prime Index. Finally, the Edge Prime Index of some graphs are found. Keywords: Prime Labeling, Relatively Prime Edge Labeling, Coprime Edge Labeling, Prime Index, Edge Prime Index. 1. Introduction Labeling plays a significant role in the field of graph theory. To meet out the current needs different types of labeling are emerging now a days (2, 9). One such labeling is prime labeling. In prime labeling, vertices are labeled from 1 to n, with the condition that any two adjacent vertices have relatively prime labels (1). From the knowledge attained from prime labeling, Relatively Prime Edge Labeling technique focuses on labeling the edges such that adjacent edges have relatively prime labels, unlike prime labeling, which assigns relatively prime labels to adjacent vertices. A graph that allows relatively prime edge labeling is known as a relatively prime edge-labeled graph. Coprime labeling is another labeling technique that is derived from prime labeling (3, 4). In coprime labeling, the labels are not limited to 1 to n as in prime labeling. If the vertices are labeled from 1 to k, then the least k is called the minimum coprime number of G. Inspired by the above research, coprime edge labeling is employed when a graph does not have a relatively prime edge labeling. In relatively prime edge labeling, the edges are labeled using numbers from 1 to q. However, coprime edge labeling does not have any restrictions on the labels used for the edges. A prime graph G is a bijection f ∢ V β†’ {1,2,3 … . , p} such that, for each edge e = uv οƒŽ E, we have GCD (f(u), f(v)) = 1 (2). Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 43 https://internationalpubls.com Definition 1.1 Let G = (V, E) be a graph. A bijection 𝑓 ∢ 𝐸 β†’ {1,2,3 … … π‘ž } is called relatively prime edge labeling if, for each vertex v οƒŽ V(G), the labels of the edge’s incident on 𝑣 are pairwise relatively prime. A graph that admits a relatively prime edge labeling is called a relatively prime edge labeled graph. (8) In other words, a graph with 𝑝 vertices and π‘ž edges are said to be a relatively prime edge labeled graph, if the edges are labeled with the first q natural numbers with the condition that any two adjacent edges have relatively prime labels. Considering, edge incident on pendent vertex as relatively prime. (8) Definition 1.2 For a graph, G = (p, q), coprime edge labeling is defined to be a bijection 𝑓: 𝐸 β†’ {1, 2, . . . , π‘˜} such that, for π‘˜ β‰₯ π‘ž , and for each vertex v οƒŽ V, the labels of the edge’s incident on 𝑣 are pairwise relatively prime. (10) The minimum value of π‘˜, for which G is coprime edge labeling is called as minimum coprime edge labeling, with minimum coprime edge number, π‘πœπΈ(𝐺) = π‘˜. Definition 1.3 For a coprime graph G, the prime index is the least number of edges removed from G to form a prime graph G*. And is denoted by, Ξ΅(G). In other words, (10) Ξ΅(G) = min {| E(H) | ∢ H βŠ† G and G βˆ’ E(H) is prime} 2. Edge Prime Index In this section, the formal definition of Edge Prime Index is defined with an appropriate example. 2.1. Definition Edge Prime Index: Let G be a coprime edge labeled graph. Edge Prime Index πœ€π‘Ÿ(𝐺) is defined to be the minimum number of edges removed from G to form a relatively prime edge labeled graph πΊβˆ—. In other words, πœ€π‘Ÿ(𝐺) = π‘šπ‘–π‘›{| 𝐸(𝐻) | ∢ 𝐻 βŠ† 𝐺 & 𝐺 βˆ’ 𝐸(𝐻) 𝑖𝑠 π‘Ÿπ‘’π‘™π‘Žπ‘‘π‘–π‘£π‘’π‘™π‘¦ π‘π‘Ÿπ‘–π‘šπ‘’ 𝑒𝑑𝑔𝑒 π‘™π‘Žπ‘π‘’π‘™π‘’π‘‘ π‘”π‘Ÿπ‘Žπ‘β„Ž} 2.2.Illustration For a complete graph 𝐾4 , the edge prime index is explained in the given figure 1. That is, by removing an edge from 𝐾4 , it becomes a relatively prime edge labeled graph. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 44 https://internationalpubls.com Figure 1: Ξ΅r(K4) = 1 3. Relation with Other Parameters The next theorem helps to find the upper bound of the edge prime index of a graph having a Hamiltonian circuit (7). Theorem 3.1 For a graph 𝐺 = (𝑝, π‘ž) which contains a Hamiltonian circuit of length k, then Ξ΅r(G) ≀ π‘ž βˆ’ π‘˜. Proof. Suppose, Ξ΅r(G) > π‘ž βˆ’ π‘˜, where k is the length of the Hamiltonian circuit and q is the number of edges. Let 𝑣1, 𝑣2, β‹― , 𝑣𝑝 be the p vertices. As G contains a Hamiltonian circuit of length k, say 𝑣1, 𝑣2, β‹― , π‘£π‘˜ then label the edges of the Hamiltonian circuit in such a way that, L(vivi+1) = i for 𝑖 = 1, 2, … , π‘˜ π‘Žπ‘›π‘‘ π‘£π‘˜+1 = 𝑣1. Since the prime index is greater than π‘ž βˆ’ π‘˜ , which is the contradiction to the above labeling. Hence the maximum number of edges to be removed from G is less than or equal to π‘ž βˆ’ π‘˜ . Corollary 3.2 For a complete graph 𝐾4 , Ξ΅r(𝐾4 ) ≀ 2. Proof. By the above theorem, Figure 2 shows that, 𝐾4 contains a Hamiltonian circuit of length 4 and the number of edges in 𝐾4 is 6. Hence Ξ΅r(G) ≀ 6 βˆ’ 4 = 2. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 45 https://internationalpubls.com Figure 2: Complete graph with 4 vertices 4. Edge Prime Index of Some Class of Graphs In this section, Edge Prime Index is found for specific classes of graphs, namely the complete graph, the corona product of graphs and so on (7). 4.1. Corona Product of Graph In the following theorem, the relatively prime index of the corona product of Kn and K1 is determined. The corona product of two graphs G and H is defined as the graph obtained by taking one copy of G and |V(G)| copies of H and joining the ith vertex of G to every vertex in the ith copy of H. Theorem 4.1 For a graph Kn βŠ™ K1, πœ€π‘Ÿ(Kn βŠ™ K1) = { 𝑛(π‘›βˆ’3) 2 , 𝑖𝑓 2𝑛 + 1 ≑ 0(π‘šπ‘œπ‘‘ 3) 𝑛(π‘›βˆ’3) 2 βˆ’ 1 , 𝑖𝑓 2𝑛 + 1 β‰’ 0(π‘šπ‘œπ‘‘ 3) Proof Let G = Kn βŠ™ K1 be the graph with 2n vertices and 𝑛(𝑛+1) 2 edges and let 𝑣1, 𝑣2, β‹― β‹― , 𝑣𝑛, 𝑒1, 𝑒2, β‹― β‹― , 𝑒𝑛 be the vertices of Kn βŠ™ K1. Case 1: For 2𝑛 + 1 ≑ 0(π‘šπ‘œπ‘‘ 3). It is enough to prove that, the removal of 𝑛(π‘›βˆ’3) 2 edges results in a relatively prime edge labeled graph. Suppose the removal of 𝑛(π‘›βˆ’3) 2 βˆ’ 1 edges in Kn βŠ™ K1 results in a relatively prime edge labeled graph. That is, remaining 𝑛(𝑛+1) 2 βˆ’ 𝑛(π‘›βˆ’3) 2 + 1 = 2𝑛 + 1 edges of Kn can be labeled from 1 to 2𝑛 + 1. Hence by removing 𝑛(π‘›βˆ’3) 2 βˆ’ 1 interior edges of Kn βŠ™ K1, the resultant graph will be of the form Cn with n edges, n pendent vertices (𝑒1, 𝑒2, β‹― β‹― , 𝑒𝑛) connecting to the each vertex of Cn and an edge connecting any two non-adjacent vertices of Cn . Each vertex 𝑣1, 𝑣2, β‹― β‹― , 𝑣𝑛 of Cn is of degree 3. By labeling the edges of Cn with 1, 3, 5, … . 2𝑛 βˆ’ 1 , each edge incident on the pendant vertices is labeled with 2, 4, 6, … , 2𝑛 and an edge connecting any two non-adjacent vertices of Cn is labeled with Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 46 https://internationalpubls.com 2𝑛 + 1. As 2𝑛 + 1 ≑ 0(π‘šπ‘œπ‘‘ 3), that is 2𝑛 + 1 = 3π‘š, the label incident on the vertices of the edge with label 2𝑛 + 1 fails to be relatively prime. Case 2: For 2𝑛 + 1 β‰’ 0(π‘šπ‘œπ‘‘ 3). It is enough to prove that, the removal of 𝑛(π‘›βˆ’3) 2 βˆ’ 1 edges results in a relatively prime edge labeled graph. Suppose the removal of 𝑛(π‘›βˆ’3) 2 βˆ’ 2 edges in Kn βŠ™ K1 results in a relatively prime edge labeled graph. That is, remaining 𝑛(𝑛+1) 2 βˆ’ 𝑛(π‘›βˆ’3) 2 + 2 = 2𝑛 + 2 edges of Kn can be labeled from 1 to 2𝑛 + 2. Hence by removing 𝑛(π‘›βˆ’3) 2 βˆ’ 2 interior edges of Kn βŠ™ K1, the resultant graph will be of the form Cn with n edges, n pendent vertices (𝑒1, 𝑒2, β‹― β‹― , 𝑒𝑛) connecting to the each vertex of Cn and two edges connecting any two non-adjacent vertices of Cn . Each vertex 𝑣1, 𝑣2, β‹― β‹― , 𝑣𝑛 of Cn is of degree 3. By labeling the edges of Cn with 1, 3, 5, … . 2𝑛 βˆ’ 1 , each edge incident on the pendant vertices is labeled with 2, 4, 6, … , 2𝑛 and the edge connecting any two non-adjacent vertices of Cn is labeled with 2𝑛 + 1, 2𝑛 + 2. As 2𝑛 + 1 β‰’ 0(π‘šπ‘œπ‘‘ 3), the label incident on the vertices of the edge with label 2𝑛 + 2 fails to be relatively prime. Illustration As an illustration of above theorem, edge prime index of , K4 βŠ™ K1 π‘Žπ‘›π‘‘ , K5 βŠ™ K1 is given in Figure – 3, 4 respectively. For 2𝑛 + 1 ≑ 0(π‘šπ‘œπ‘‘ 3), consider n = 4 that is, K4 βŠ™ K1, the edge prime index is πœ€π‘Ÿ(K4 βŠ™ K1) = 𝑛(π‘›βˆ’3) 2 = 4 2 = 2 , which is illustrated in Figure 3. Figure 3: Edge Prime Index πœ€π‘Ÿ(K4 βŠ™ K1) = 2 For 2𝑛 + 1 β‰’ 0(π‘šπ‘œπ‘‘ 3), consider n = 5, that is K5 βŠ™ K1. . Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 47 https://internationalpubls.com The edge prime index of K5 βŠ™ K1. is πœ€π‘Ÿ(K5 βŠ™ K1) = 𝑛(π‘›βˆ’3) 2 βˆ’ 1 = 5Γ—2 2 βˆ’ 1 = 4, which is illustrated in Figure 4. Figure 4: Edge Prime Index πœ€π‘Ÿ(K5 βŠ™ K1) = 4 4.2. Complete Bipartite Graph The following theorem finds the edge prime index of the complete bipartite graph 𝐾2,𝑑 and 𝐾3,𝑑 with proper illustration (7) . Theorem 4.2 For a graph G = 𝐾2,𝑑 , 𝑑 > 2 then, Ξ΅r(G) = 2𝑑 βˆ’ 5. Proof. We know that, 𝐺 = 𝐾2,𝑑 is not RPEL graph. Now, it is enough to find the minimum number of edges to be removed from G to make G as a RPEL. The number of vertices and edges in 𝐺 = 𝐾2,𝑑 is 𝑑 + 2 π‘Žπ‘›π‘‘ 2𝑑. Label the edges of G in such a way that, 𝐿(𝑒1𝑣1) = 1, 𝐿(𝑒1𝑣2) = 2 , 𝐿(𝑒1𝑣3) = 3 , 𝐿(𝑒1𝑣4) = 5 π‘Žπ‘›π‘‘ 𝐿(𝑒2𝑣1) = 4 as in Figure 5. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 48 https://internationalpubls.com Figure 5 Edge Prime Index Illustration Also, the label 6 cannot be labeled in any of the edge’s incident on 𝑒1 and 𝑒2. Thus, it is needed to remove 2𝑑 βˆ’ 5 edges from G to make it as a relatively prime edge labeled graph. Hence, Ξ΅r(G) = 2𝑑 βˆ’ 5. Theorem 4.3. For a graph G = 𝐾3,𝑑 , 𝑑 > 3, then, Ξ΅r(G) = 3𝑑 βˆ’ 7. Proof. Since 𝐺 = 𝐾3,𝑑 is not RPEL graph. It is enough to find the minimum number of edges to be removed from G to make it as a RPEL graph. The number of vertices and edges in 𝐺 = 𝐾3,𝑑 is 𝑑 + 3 π‘Žπ‘›π‘‘ 3𝑑. Label the edges of G in such a way that, 𝐿(𝑒1𝑣1) = 1, 𝐿(𝑒1𝑣2) = 2 , 𝐿(𝑒1𝑣3) = 3 , 𝐿(𝑒1𝑣4) = 5 , 𝐿(𝑒2𝑣1) = 4, 𝐿(𝑒2𝑣2) = 7 and , 𝐿(𝑒3𝑣4) = 6 as in Figure 6. Figure 6 Edge Prime Index Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 49 https://internationalpubls.com Also, the label 8 cannot be labeled in any of the edge’s incident on 𝑒1, 𝑒2 and 𝑒3. Thus, it is needed to remove 3𝑑 βˆ’ 7 edges from G to make it as a relatively prime edge labeled graph. Hence, Ξ΅r(G) = 3𝑑 βˆ’ 7. 4.3. Generalized Petersen Graph The next theorem finds the edge prime index of the Generalized Petersen Graph G = P(n, k). The Generalized Petersen graphs P(n, k) with n β‰₯ 3 and 1 ≀ k ≀ n 2 are defined to be a graph with V(P(n, k)) = {uj , vj ∢ 1 ≀ j ≀ n} and E(P(n, k)) = {v1vj+1 , vjuj, ujuj+k ∢ 1 ≀ j ≀ n, subscript mod n }. (5,6) Theorem 4.4. For even n, the generalized Petersen graph G = P(n, 2) then, Ξ΅r(G) = 𝑛 βˆ’ 1. Proof The vertices of P(n, 2) are { 𝑣1, 𝑣2 …. 𝑣𝑛, 𝑒1, 𝑒2, … , 𝑒𝑛 }, where 𝑣1, 𝑣2 …. 𝑣𝑛 represents the outer vertices and 𝑒1, 𝑒2, … , 𝑒𝑛 represents the inner vertices and the edges of P(n, 2) are { 𝑣1𝑣𝑖+1, 𝑣𝑖 𝑒𝑖 , 𝑒𝑖𝑒𝑖+2 : 1 ≀ 𝑖 ≀ 𝑛 , subscript mod 𝑛 }. Thus, there are 2n vertices and 3n edges in P(n, 2). As the gcd(n, 2) = 2, for even n, there exists 2 disjoint inner cycles of length 𝑛 2 each and there exists an outer cycle {𝑣1 𝑣2 …. 𝑣𝑛𝑣1} of length n. Now, label the edges of P(n, 2) in such a way that, the two inner cycles receive the label {1, 2, 3, … . , 𝑛 2 } π‘Žπ‘›π‘‘ { 𝑛+2 2 , … . , 𝑛} and the outer cycle with {𝑛 + 1, 𝑛 + 2, … . . 2𝑛}. As 2𝑛 + 1 is odd, label any of the edge {𝑣𝑖 𝑒𝑖} as 2𝑛 + 1. Also, 2𝑛 + 2 cannot be labeled on any edge because 2𝑛 + 2 is an even number that violates the relative prime property. Thus, the relatively prime index of P(n, 2) for even n, is Ξ΅r(P(n, 2)) = 3𝑛 βˆ’ 2𝑛 βˆ’ 1 = 𝑛 βˆ’ 1 . Hence the proof. Illustration: Figure 7 shows the illustration of the above theorem. Consider a generalized Petersen Graph with 16 vertices, P(8,2) . Then the edge prime index is given by, Ξ΅r(P(8 ,2)) = 𝑛 βˆ’ 1 = 8 βˆ’ 1 = 7 Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 50 https://internationalpubls.com Figure 7: Ξ΅r(P(8 ,2)) = 7 Theorem 4.5. For even n, k, the generalized Petersen graph G = P(n, k) then, Ξ΅r(G) = 𝑛 βˆ’ 1. Proof: The vertices of P(n, k) are { 𝑣1, 𝑣2 …. 𝑣𝑛, 𝑒1, 𝑒2, … , 𝑒𝑛 }, where 𝑣1, 𝑣2 …. 𝑣𝑛 represents the outer vertices and 𝑒1, 𝑒2, … , 𝑒𝑛 represents the inner vertices and the edges of P(n, k) are { 𝑣1𝑣𝑖+1, 𝑣𝑖 𝑒𝑖 , 𝑒𝑖𝑒𝑖+π‘˜ : 1 ≀ 𝑖 ≀ 𝑛 , subscript mod 𝑛 }. We know that, there exist gcd(n, k) = d inner cycles of length 𝑛 π‘˜ each. Label the edges of P(n, k) in such a way that, the d inner cycles receive the label {1, 2, 3, … . , 𝑛 } consecutively and the outer cycle with {𝑛 + 1, 𝑛 + 2, … . . 2𝑛}. As 2𝑛 + 1 is odd, label any of the edge {𝑣𝑖 𝑒𝑖} as 2𝑛 + 1. Also, 2𝑛 + 2 cannot be labeled on any edge because 2𝑛 + 2 is an even number that violates the relative prime property. Thus, the edge prime index of P(n, k) for even n, k , is Ξ΅r(P(n, k)) = 3𝑛 βˆ’ 2𝑛 βˆ’ 1 = 𝑛 βˆ’ 1 . Hence the proof. 4.4. Ladder Graph The ladder graph L(n) consists of two parallel paths, each with n vertices, and these paths are connected by n-1 edges known as "rails." The first and last vertices of each path are also connected by an additional edge called the "rung." Therefore, a ladder graph L(n) has a total of 2n vertices and 3n-2 edges. In this section, the edge prime index of the ladder graph L(n) is discussed. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 51 https://internationalpubls.com Theorem 4.6. For a ladder graph G = 𝐿𝑛 , 𝑛 > 3 then, Ξ΅r(G) = 𝑛 βˆ’ 3. Proof: Let the vertices in the Ladder graph are { 𝑣1, 𝑣2 …. 𝑣𝑛, 𝑒1, 𝑒2, … , 𝑒𝑛 }. Then by the definition of ladder graph, there are 2n and 3n-2 vertices and edges respectively. Now, it is enough to find the minimum number of edges to be removed from the ladder graph to make it as a relatively prime edge labeled graph. The maximal cycle formed by the vertices of the ladder graph is 𝑣1, 𝑣2 …. 𝑣𝑛, 𝑒𝑛, π‘’π‘›βˆ’1, … , 𝑒1,, 𝑣1. Now, label the edges of G in such a way that, the maximal cycle is labeled with { 2, 3, … . , 2𝑛 + 1} and the edge 𝑒2𝑣2 with the label 1 as shown in figure 8. Figure 8: Ξ΅r(G) = n βˆ’ 3 Also, 2n+2 is an even number and to make the edges incident of each vertex as pairwise relatively prime, it cannot be labeled in any of the edges. Thus, Ξ΅r(G) = 3𝑛 βˆ’ 2 βˆ’ 2𝑛 βˆ’ 1 = 𝑛 βˆ’ 3. Hence the proof. 4.5. Powers of Paths and Cycle For the powers of path and cycle graph, the edge prime index is determined in this section. The m-th power of a simple graph G can be defined as the graph πΊπ‘š, where the set of vertices in πΊπ‘š is the same Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 52 https://internationalpubls.com as that in G. In πΊπ‘š , two vertices are adjacent if and only if their distance in G is not more than m. That is, their distance in G is at most π‘š. Theorem 4.7. For even n, the power graph of a path G = P𝑛 2, then, Ξ΅r(G) = { 𝑛 βˆ’ 3 𝑖𝑓 𝑛 𝑖𝑠 π‘œπ‘‘π‘‘ 𝑛 βˆ’ 4 𝑖𝑓 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛 Proof: Let the number of vertices and edges in 𝑃𝑛 2 are 𝑛 and 2𝑛 βˆ’ 3 respectively. From the definition of 𝑃𝑛 2, there exists a maximal cycle of length n. Now, label the maximal cycle with {1, 2, 3, … . . . , 𝑛}. Case 1: n is odd As n is odd, 𝑛 + 1 is even. Hence it is not possible to label 𝑛 + 1 in any of the remaining edges. Because the remaining edges associated with a vertex already contains the label of even multiple. Thus, by labeling 𝑛 + 1 will violate the relatively prime property. Therefore, it is necessary to remove 2𝑛 βˆ’ 3 – 𝑛 = 𝑛 βˆ’ 3 edges from P𝑛 2 to make it as a relatively prime labeled graph. That is, Ξ΅r(G) = 𝑛 βˆ’ 3. (Example for 𝑛 = 7 is illustrated in Figure 9) Figure 9: Ξ΅r(G) = n βˆ’ 3 = 4 Case 2: n is even As n is even, 𝑛 + 1 is odd. Hence it is possible to label 𝑛 + 1 in any of the remaining edges. And, it is not possible to label 𝑛 + 2 in the remaining edges. Therefore, it is necessary to remove 2𝑛 βˆ’ 3 – 𝑛 βˆ’ 1 = 𝑛 βˆ’ 4 edges from P𝑛 2 to make it as a relatively prime labeled graph. That is, Ξ΅r(G) = 𝑛 βˆ’ 4. (Example for 𝑛 = 8 is illustrated in Figure 10) Figure 10: Ξ΅r(G) = n βˆ’ 4 = 4 Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 53 https://internationalpubls.com Theorem 4.8. For a power graph of a cycle G = C𝑛 2 , then, Ξ΅r(G) = { 𝑛 𝑖𝑓 𝑛 𝑖𝑠 π‘œπ‘‘π‘‘ 𝑛 βˆ’ 1, 𝑖𝑓 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛 Proof: Let the number of vertices and edges in 𝐢𝑛 2 are 𝑛 and 2𝑛 respectively. From the definition of 𝐢𝑛 2, there exists a cycle of length n. Now, label the cycle with {1, 2, 3, … . . . , 𝑛}. Case 1: n is odd As n is odd, 𝑛 + 1 is even. Hence it is not possible to label 𝑛 + 1 in any of the remaining edges. Because the remaining edges associated with a vertex already contains the label of even multiple. Thus, by labeling 𝑛 + 1 will violate the relatively prime property. Therefore, it is necessary to remove 2𝑛 – 𝑛 = 𝑛 edges from C𝑛 2 to make it as a relatively prime labeled graph. That is, Ξ΅r(G) = 𝑛 (Example for 𝑛 = 5 is illustrated in Figure 11) Figure 11: Ξ΅r(G) = n = 5 Figure 12: Ξ΅r(G) = n βˆ’ 1 = 5 Case 2: n is even As n is even, 𝑛 + 1 is odd. Hence it is possible to label 𝑛 + 1 in any of the remaining edges. And, it is not possible to label 𝑛 + 2 in the remaining edges. Therefore, it is necessary to remove 2𝑛 – 𝑛 βˆ’ 1 = 𝑛 βˆ’ 1 edges from C𝑛 2 to make it as a relatively prime labeled graph. That is, Ξ΅r(G) = 𝑛 βˆ’ 1. (Example for 𝑛 = 6 is illustrated in Figure 12) References [1] A. Tout, A. N. Dabboucy, K. Howalla, 1982, Prime labeling of graphs, Nat. Acad. Sci. Letters, 11, 365-368. [2] J. A. Gallian, 2018. A Dynamic Survey of Graph Labeling, Electronic Journal of Combinatorics, vol. 1. [3] J. Asplund, N. Bradley Fox, 2017, Minimum Coprime Labelings for Operations on Graphs, Integers, pp. 1–19. [4] A. H. Berliner, N. Dean, J. Hook, A. Marr, A. Mbirika, C. D. McBee, 2016, Coprime and prime labelings of graphs, J. Integer Seq., 19(5). [5] K. M. M. Haque, L. Xiaohui, Y. Yuansheng, Z. Pingzhong, 2010. On the prime labeling of generalized Petersen graph P (n, 1). Utilitas Mathematica, 83. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 54 https://internationalpubls.com [6] U. M. Prajapati, S. J. Gajjar. 2015, Prime labeling of generalized Petersen graph, Internat. J. Math. and Soft Comput 5: 65-71. [7] N Deo, 1974. Graph Theory with applications to Engineering and computer science, Courier Dover Publications, 2017. [8] R. Janani, and T. Ramachandran, On Relatively Prime Edge Labeling of Graphs, Engineering Letters. 30(2), 659- 665 (2022). [9] Janani R, Ramachandran T, Applications of Labeling in Hypergraph, International Research Journal of Multidisciplinary Scope, 5 (1), 379- 386. [10] Janani, R., and T. Ramachandran, On Prime Index of a Graph. Ratio Mathematica 48 (2023). DOI: http://dx.doi.org/10.23755/rm.v48i0.1315 http://dx.doi.org/10.23755/rm.v48i0.1315