Ratio Mathematica Volume 47, 2023 Relatively Prime Inverse Domination on Line Graph C. Jayasekaran* L. Roshini† Abstract Let G be non-trivial graph. A subset D of the vertex set V (G) of a graph G is called a dominating set of G if every vertex in V − D is adjacent to a vertex in D. The minimum cardinality of a dominating set is called the domination number and is denoted by γ(G). If V −D contains a dominating set S of G, then S is called an inverse domi- nating set with respect to D. In an inverse dominating set S, every pair of vertices u and v in S such that (deg(u), deg(v)) = 1, then S is called relatively prime inverse dominating set. The minimum cardi- nality of a relatively prime inverse dominating set is called relatively prime inverse dominating number and is denoted by γ−1rp (G). In this paper we find relatively prime inverse dominating number of some jump graphs. Keywords: Domination number, Inverse domination number, Rela- tively prime domination number. 2020 AMS subject classifications: 05C69,05C76 1 *Associate Professor, Department of Mathematics, Pioneer Kumaraswamy College, Nagercoil - 629003, Tamil Nadu, India; jayacpkc@gmail.com. †Research Scholar, Department of Mathematics, Pioneer Kumaraswamy College, Nagercoil - 629003, Tamil Nadu, India. Affliated to Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli - 627012,Tamil Nadu, India.; jerryroshini92@gmail.com. 1Received on November 10, 2022. Accepted on March 24, 2023. Published on April 4, 2023. DOI: 10.23755/rm.v41i0.954. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper is published under the CC-BY licence agreement. 332 C. Jayasekaran, L. Roshini 1 Introduction By a graph, we mean a finite undirected graph with neither loops nor mul- tiple edges. For graph theoretic terminology, we refer to the book by Chartrand and Lesniak [1]. All graphs in this paper are assumed to be non-trivial. In a graph G = (V, E), the degree of a vertex v is defined to be the number of edges incident with v and is denoted by deg(v). A set D of vertices of graph G is said to be a dominating set if every vertex in V −D is adjacent to a vertex in D. A dominating set D is said to be a minimal dominating set if no proper subset of D is a dom- inating set. The minimum cardinality of a dominating set of a graph G is called the domination number of G and is denoted by γ(G). Kulli V. R. et al. introduced the concept of inverse domination in graphs [8]. Let D be a minimum dominating set of G. If V − D contains a dominating set S, then S is called a inverse domi- nation set of G with respect to D. The inverse domination number γ−1(S) is the minimum cardinality taken over all the minimal inverse dominating set of G. The Jewel graph Jn is a graph with vertex set V (Jn) = {u, x, v, y, vi : 1 ≤ i ≤ n} and edge set E(Jn) = {ux, vx, uy, vy, xy, uvi, vvi : 1 ≤ i ≤ n}[7]. Bistar Bm,n is the graph obtained by joining the center vertices of star graphs K1,m and K1,n by an edge. The vertex set of Bm,n is {u, v, ui, vj : 1 ≤ i ≤ m, 1 ≤ j ≤ n} where u, v are apex vertices and ui, vi are pendent vertices. The edge set of Bm.n is {uv, uui, vvj : 1 ≤ i ≤ n, 1 ≤ j ≤ m} and |V (Bm,n)| = m+n+2, |E(Bm,n)| = m + n + 1[2]. A spider graph is a tree with at most one vertex of degree greater than 2[2]. Let Pn be a path graph with n vertices. The Comb graph is defined as Pn ⊙ K1. It has 2n vertices and 2n − 1 edges[3]. A wounded spider graph is a graph obtained by subdividing at most n − 1 edges of a star K1,n. The wounded spider includes K1, the star K1,n−1[9]. A set S ⊆ V is said to be relatively prime dominating set if it is a dominating set with at least two elements and for every pair of vertices u and v in S such that (deg(u), deg(v)) = 1. The minimum car- dinality of a relatively prime dominating set of a graph G is called the relatively prime domination number of G and is denoted by γrpd(G) [5]. The purpose of this paper is to study about the concept of relatively prime inverse domination on line graphs. Definition 1.1. [6]Let D be a minimum dominating set of a graph G. If V − D contains a dominating set S of G, then S is called an inverse dominating set with respect to D. If every pair of vertices u and v in S such that (deg(u), deg(v)) = 1, then S is called relatively prime inverse dominating set. The minimum cardinality of a relatively prime inverse dominating set is called a relatively prime inverse domination number and is denoted by γ−1rp (G). If the relatively prime inverse dominating set is absent, then γ−1rp (G) = 0. Definition 1.2. [4]A line graph L(G) of a simple graph G is obtained by associ- 333 Relatively Prime Inverse Domination on Line Graph ating a vertex with each edge of the graph and connecting two vertices with an edge if only if the corresponding edges of G have a vertex in common. Example 1.1. Consider the graphs G and L(G) which are given Figure 1. Clearly {e1, e4} is a minimum dominating set of L(G) and {e2, e5} is a corresponding minimum inverse dominating set of L(G) and (deg(e1), deg(e4)) = (4, 3) = 1 and so γ−1rp L(G) = 2. G L(G) Figure 1: G, L(G) u2 u6 u5 e4 u1 e5 e1u3 e2 u4 e7 e6 e3 e8 e1 e2 e3 e4 e5 e6 e7 e8 We use the following theorem: Theorem 1.1. [8] For a path Pn, γ−1rp (Pn) =   2 if 3 ≤ n ≤ 5 3 if n = 6, 7 0 otherwise 2 Relatively prime inverse domination on line graph Theorem 2.1. For the spider graph K1,n,n, γ−1rp (L(K1,n,n)) = n. Proof. Let v be the centre vertex and the end vertices of K1,n be v1, v2, ..., vn. Let u1, u2, ..., un represent the vertices connected with v1, v2, ..., vn, respectively. The resulting graph is the spider graph K1,n,n with vertex set V (K1,n,n) = {v, vi, v ′ i : 1 ≤ i ≤ n} and E(K1,n,n) = {vvi, viv ′ i : 1 ≤ i ≤ n}. Clearly, deg(v) = n, deg(vi) = 2, and deg(v ′ i) = 1, 1 ≤ i ≤ n. Let the line graph of the graph K1,n,n be L(K1,n,n). Denote the edges vvi by ei and viv ′ i by e ′ i . Clearly V (L(K1,n,n)) = {ei, e ′ i : 1 ≤ i ≤ n} and E(L(K1,n,n)) = {eiej, eie ′ i : 1 ≤ i ̸= j ≤ n}. Let D be a minimum dominating set of L(K1,n,n) and S be a corresponding mini- mum inverse dominating set of L(K1,n,n). Although L(K1,n,n) contains n end 334 C. Jayasekaran, L. Roshini vertices, any minimum dominating set of L(K1,n,n) must include at least n ver- tices of L(K1,n,n). Clearly, D = {ei : 1 ≤ i ≤ n} is a minimum dominating set and S = {e′i : 1 ≤ i ≤ n} is the corresponding minimum inverse dominating set of L(K1,n,n). Since deg(e ′ i) = deg(e ′ j) = 1 for 1 ≤ i ̸= j ≤ n, S is a minimum rela- tively prime inverse dominating set of L((K1,n,n)). As a result, γ−1rp (L(K1,n,n)) = n. K1,4,4 L(K1,4,4) Figure 2: K1,4,4, L(K1,4,4) v e1 e2 e3 e4 e ′ 1 e ′ 2 e ′ 3 e ′ 4 v1 v2 v3 v4 v ′ 1 v ′ 2 v ′ 3 v ′ 4 e1 e2 e3e4 e ′ 1 e ′ 4 e ′ 3 e ′ 2 Theorem 2.2. For the wounded spider graph K1,n,s, γ−1rp (L(G)) = s + 1 where s < n. Proof. Let v be the centre vertex and v1, v2, ..., vn be the end vertices of K1,n. Attach u1, u2, ..., us to v1, v2, ..., vn as appropriate where s < n. The resulting graph is the wounded spider graph K1,n,s with vertex set V (K1,n,s) = {v, vi, uj : 1 ≤ i ≤ n, 1 ≤ j ≤ s} and E(K1,n,s) = {vvi, vjuj : 1 ≤ i ≤ n, 1 ≤ j ≤ s}. Clearly in K1,n,s, deg(v) = n, deg(vi) = 2, 1 ≤ i ≤ s, deg(vk) = 1, s+1 ≤ i ≤ n and deg(ui) = 1, 1 ≤ i ≤ s. Let the line graph of the graph K1,n,s be L(K1,n,s) where we denote the edge vvi by ei and vjuj by e ′ j, 1 ≤ i ≤ n, 1 ≤ j ≤ s. Clearly, V (L(K1,n,s)) = {ei, e ′ j : 1 ≤ i ≤ n, 1 ≤ j ≤ s} and E(L(K1,n,s)) = {eiek, eje ′ j : 1 ≤ i ̸= k ≤ n, 1 ≤ j ≤ s}. Also in L(K1,n,s), deg(ej) = n, deg(e ′ j) = 1 and deg(ei) = n − 1, 1 ≤ j ≤ s and s + 1 ≤ i ≤ n. Let D be a minimum domi- nating set of L(K1,n,s) and S be a minimum inverse dominating set of L(K1,n,s) with respect to D. Since L(K1,n,s) contains s end vertices, any minimum dom- inating set of L(K1,n,s) must include at least s vertices of L(K1,n,s). Clearly, D = {ej : 1 ≤ j ≤ s} and S = {en, e ′ j : 1 ≤ j ≤ s} is a corresponding mini- mum inverse dominating set of L(K1,n,s). Since the degree sequence of vertices in S is (n, 1, 1, ..., 1), S is a minimum relatively prime inverse dominating set of L((K1,n,s)) and hence γ−1rp (L(K1,n,s)) = s + 1. 335 Relatively Prime Inverse Domination on Line Graph K1,5,3 L(K1,5,3) Figure 3: K1,5,3, L(K1,5,3) v v1 e1 v3 e3 v5 e5 v2 e2 v4 e4 u1 e ′ 1 u2 e ′ 2 u3 e ′ 3 e4 e5 e1 e2 e3 e ′ 2 e ′ 1 e ′ 3 Theorem 2.3. For the jewel graph Jn, γ−1rp (L(Jn)) = 2 if n ≥ 1. Proof. Consider a 4-cycle xwyux. Join x and y. Now adding n new vertices vi, 1 ≤ i ≤ n. Join vi with u and w, 1 ≤ i ≤ n. The resulting grph is the jewel graph Jn with vertex set V (Jn) = {x, y, u, w, vi : 1 ≤ i ≤ n} and edge set E(Jn) = {ei, e ′ j, e ′′ j : 1 ≤ i ≤ 5, 1 ≤ j ≤ n}, where e1 = xw, e2 = wy, e3 = yu, e4 = ux, e5 = xy, e ′ j = uvj, e ′′ j = wvj. Let the line graph of Jn be L(Jn) where V (L(Jn)) = E(Jn) = {ei, e ′ j, e ′′ j : 1 ≤ i ≤ 5, 1 ≤ j ≤ n} and E(L(Jn)) = {eiei+1, e1e4, e5ej, e ′ jei, e ′ je ′ k, e ′′ j em, e ′′ j e ′′ p : 1 ≤ i ≤ 3, 1 ≤ j ≤ k, p ≤ n, 3 ≤ l ≤ 4, 1 ≤ m ≤ 2}, i ̸= k. Let D be a minimum dominating set of L(Jn) and S be a corresponding minimum inverse dominating set. In L(Jn), the number of vertices is 2n + 5 and the maximum degree is 2n − 1 and so any minimum dominating set contains at least two vertices. Now e1 is adjacent to all vertices except e3 and e ′ i, 1 ≤ i ≤ n; e ′ 1 is adjacent to e3, e4, e ′′ 1 and e ′ i, 2 ≤ i ≤ n. Hence D = {e1, e ′ 1} is a minimum dominating set of L(Jn). Clearly, S = {e3, e ′′ 1} ⊆ V − D is also a minimum dominating set of L(Jn). Hence, S is a minimum inverse dominating set of L(Jn). In L(Jn), deg(e3) = n + 3, deg(e ′′ 1) = n + 2 and therefore (deg(e3), deg(e ′′ 1)) = (n + 3, n + 2) = 1. This implies that S is a minimum relatively prime inverse dominating set of L(Jn) and so γ−1rp (L(Jn)) = 2. . 336 C. Jayasekaran, L. Roshini J1 L(J1) Figure 4: J1, L(J1) e4 e1 exy e2e3 e ′ 1 e ′′ 1 u x w y v1 e ′ 1 e ′′ 1 e1 e2 e3 e4 exy Theorem 2.4. For the bistar graph Bm,n, γ−1rp (L(Bm,n)) = { 2 if (m, n) = 1 0 otherwise . Proof. A bistar graph Bm,n consists of two star graphs K1,m and K1,n having center vertices u0 and v0 respectively. Join u0 and v0 with an edge. The resulting graph is a bistar graph Bm,n with the vertex set V (Bm,n) = {ui, vj : 0 ≤ i ≤ m, 0 ≤ j ≤ n} and edge set E(Bm,n) = {u0ui, v0vj, u0v0 : 1 ≤ i ≤ m, 1 ≤ j ≤ n}. Let the line graph of Bm,n be L(Bm,n) with the vertex set V (L(Bm,n)) = {e0, ei, e ′ j : 1 ≤ i ≤ m, 1 ≤ j ≤ n} where e0 = u0v0, ei = u0ui, e ′ j = v0vj and edge set E(L(Bm,n)) = {e0ei, e0e ′ j, eiek, e ′ je ′ l : 1 ≤ i ̸= k ≤ m, 1 ≤ j ̸= l ≤ n}. Clearly in L(Bm,n), deg(e0) = m + n, deg(e ′ i) = m and deg(e ′ j) = n, 1 ≤ i ≤ m, 1 ≤ j ≤ n. Let D be a minimum dominating set of L(Bm,n) and S be a corresponding minimum inverse dominating set of L(Bm,n). In L(Bm,n), the vertex e0 dominates all other vertices and so the unique minimum dominating set of is D = {e0}. In V − D, each ex dominates e0 and all other ei, 1 ≤ i ≤ m and i ̸= x and also each e′y dominates all other e ′ j, j ̸= y and 1 ≤ j ≤ n. Hence a minimum inverse dominating set S = {ex, e ′ y} for some x, y where 1 ≤ x ≤ m, 1 ≤ y ≤ n. Now in L(Bm,n), (deg(ex), deg(e ′ y)) = (m, n). This implies that S is a minimum relatively prime inverse dominating set if and only if (m, n) = 1. Hence the proof. 337 Relatively Prime Inverse Domination on Line Graph B3,4 L(B3,4) Figure 5: B3,4, L(B3,4) u1 u0e2 u3 e3 u2 e1 v0 e0 v1 e ′ 1 v2 e ′ 2 v4 e ′ 4 v3e ′ 3 e ′ 3 e ′ 4 e0 e1 e2 e3 e ′ 1 e ′ 2 Theorem 2.5. For the comb graph Pn ⊙ K1, γ−1rp (L(Pn ⊙ K1)) =   2 if n = 2, 3 3 if n = 4, 5 0 otherwise . Proof. Consider the path Pn = v1v2....vn. For 1 ≤ i ≤ n, add vertex ui which is adjacent to vi. The resulting graph G = Pn ⊙ K1 is a comb graph with vertex set V (G) = {vi, ui : 1 ≤ i ≤ n} and edge set E(G) = {ei, e ′ j : 1 ≤ i ≤ n − 1, 1 ≤ j ≤ n} where ei = vivi+1, e ′ j = vjuj, 1 ≤ i ≤ n−1, 1 ≤ j ≤ n. Let the line graph of comb graph G be L(G) where the vertex set V (L(G)) = E(G) = {ei, e ′ j : 1 ≤ i ≤ n − 1, 1 ≤ j ≤ n} and edge set E(L(G)) = {eiei+1, eje ′ j, eje ′ j+1 : 1 ≤ i ≤ n − 2, 1 ≤ j ≤ n − 1}. Clearly in L(G), deg(ei) = 4, 2 ≤ i ≤ n − 2, deg(e1) = deg(en−1) = 3, deg(e ′ j) = 2, 2 ≤ j ≤ n−1 and deg(ei) = deg(e ′ n) = 1. Let D be a minimum dominating set of L(G) and S be a corresponding minimum inverse dominating set of L(G). Now we cosider the following five cases. Case 1. n = 2 Then L(G) is P3. By Theorem 1.1, γ−1rp (L(G)) = 2. 338 C. Jayasekaran, L. Roshini P2 ⊙ K1 L(P2 ⊙ K1) Figure 6: P2 ⊙ K1, L(P2 ⊙ K1) v1 v2e1 u2 e ′ 2 u1 e ′ 1 e1 e ′ 1 e ′ 2 Case 2. n = 3 In L(G), e1 is adjacent to all vertices except e ′ 3, e ′ 3 is adjacent to e2 only. Hence, D = {e1, e ′ 3} is a minimum dominating set of L(G) and a correspond- ing minimum inverse dominating set S = {e2, e ′ 1}. In L(G), (deg(e2), deg(e ′ 1)) = (3, 1) = 1. This implies that S is a minimum relatively prime inverse dominating set of L(G) and so γ−1rp (L(G)) = 2. P3 ⊙ K1 L(P3 ⊙ K1) Figure 7: P3 ⊙ K1, L(P3 ⊙ K1) u1 v1 e ′ 1 v2 e1 u2 e ′ 2 v3 e2 u3 e ′ 3 e1 e2 e ′ 1 e ′ 2 e ′ 3 Case 3. n = 4 In L(G), e1 is adjacent to all vertices except e3 and e ′ i, i = 3, 4; e ′ 3 is adjacent to all vertices except e1, e ′ i, i = 1, 2. Hence, D = {e1, e3} is a minimum dominating set of L(G) and a corresponding minimum inverse dominating set S = {e2, e ′ 1, e ′ 4}. The degree sequence vertices in S is (4,1,1). This implies that S is a minimum relatively prime inverse dominating set of L(G) and so γ−1rp (L(G)) = 3. 339 Relatively Prime Inverse Domination on Line Graph P4 ⊙ K1 L(P4 ⊙ K1) Figure 8: P4 ⊙ K1, L(P4 ⊙ K1) u1 v1 e ′ 1 v2e1 u2 e ′ 2 v3e2 u3 e ′ 3 e ′ 4 e1 e2 e3 e ′ 1e ′ 2 e ′ 3 v4e3 u4 e ′ 4 Case 4. n = 5 In L(G), e1 is adjacent to all vertices except ei, i = 3, 4, e ′ 1, e ′ 4, e ′ 5; e3 is ad- jacent to all vertices except e1, e ′ 1, e ′ 2, e ′ 5; e ′ 5 is adjacent to all vertices except e4. Hence, D = {e1, e3, e ′ 5} is a minimum dominating set and a corresponding min- imum inverse dominating S = {e2, e4, e ′ 1}. In L(G), the degree sequence of ver- tices in S is (4, 3, 1). This implies that S is a minimum relatively prime inverse dominating set of L(G) and so γ−1rp (L(G)) = 3. Case 5. n ≥ 6 The degree sequence of L(G) is {4, 4, · · · , 4(n−3)times, 3, 3, 2, 2, · · · , 2(n− 2)times, 1, 1}. Any minimum dominating set must contain at least four vertices and so any minimum inverse dominating set S as at least four vertices of dif- ferent degrees and thereby, there exists a pair of vertices (x, y) in S such that (deg(x), deg(y)) = 2 or 4. Hence, γ−1rp (L(G)) = 0. Thus the theorem following five cases. 3 Conclusion Inspired by inverse dominating set and relatively prime dominating set, we introduce the relatively prime inverse domination number on line graph. We have determined the relatively prime inverse domination on line graph of some stan- dard graphs like spider graph, wounded spider graph, jewel graph, bistar graph, and comb graph. Furthermore our results are also justified with suitable examples. 340 C. Jayasekaran, L. Roshini The relatively prime inverse domination number can be obtained for many more graphs. Acknowledgements The authors express their gratitude to the anonymous reviewers for the valu- able suggestions and comments to complete the paper. References [1] G. Chartrand, Lesniak. Graphs and Digraphs. CRC press, Boca Raton, fourth ed., 2005. [2] J. A. Gallian. A dynamic survey of graph labeling. The Electronics Journal of Combinatorics, 16(DS6), 2015. [3] E. Esakkiammal, B. Deepa, K. Thirusangu. Some Labellings on Square Graph of Comb. International Journal of Mathematics Trends and Technol- ogy(IJMTT), Special Issue NCCFQET: 28-30, 2018. [4] J. L. Gross, and J. Yellen. Graph Theory and its Applications. CRC Press,2nd ed., 2005. [5] C. Jayasekaran and A. Jancy vini. Results on relatively prime dominating sets in graphs. Annals of Pure and Applied Mathematics, 14(3): 359 – 369, 2017. [6] C. Jayasekaran and L. Roshini. Relatively prime inverse dominating sets in graphs. Malaya Journal of Matematik, 8(4): 2292-2295, 2020. [7] J. Jeba Jesitha, N.K. Vinothini and Shahina Munavar Hussain. Odd graceful Labeling for the graph jewel graph and the extended jewel graph without the prime edge. Bulletin of Pure and Applied Sciences Section-E- Mathematics and Statistics, 39E(2): 212-217, 2020. [8] V. R. Kulli and S. C. Sigarkant. Inverse domination in graphs. Nat. Acad Sci. Letters, 14: 473-475, 1991. [9] Selvam Avadayappan, M. Bhuvaeshwari and R. Iswariya. γ- Splitting Graphs. International Journal of Reasearch in Applied Science and Engineering Tech- nology(IJRASET), 4(3): 670-680, 2016. 341