Ratio Mathematica Volume 45, 2023 On the edge covering transversal edge Domination in Graphs E. Sherin Danie1 S. Robinson Chellathurai2 Abstract Let 𝐺 = (𝑉, 𝐸) be any graph with 𝑛 vertices and π‘š edges. An edge dominating set which intersects every minimum edge covering set in a graph 𝐺is called an edge covering transversal edge dominating set of 𝐺. The minimum cardinality of an edge covering transversal edge dominating set is called an edge covering transversal edge domination number of 𝐺and is denoted by𝛾𝑒𝑒𝑐𝑑 (𝐺). Any edge covering transversal edge dominating set of cardinalities𝛾𝑒𝑒𝑐𝑑 (𝐺) is called a 𝛾𝑒𝑒𝑐𝑑-set of 𝐺. The edge covering transversal edge domination number of some standard graphs are determined. Some properties satisfied by this concept are studied. Keywords: domination number, edge domination number, edge covering, edge covering number, edge covering transversal edge domination number. Mathematics Subject Classification Code: 05C69, 05C703. 1 Research Scholar, Reg. No: 19213162092014, Department of Mathematics, Scott Christian College (Autonomous), Nagercoil - 629 003, Kanyakumari District, Tamilnadu, India. (Affiliated to Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli-627 012, Tamil Nadu, India.) E-mail: *sherindanie24@gmail.com. 2 Associate professor, Department of Mathematics, Scott Christian College (Autonomous), Nagercoil - 629 003, Kanyakumari District, Tamilnadu, India. (Affiliated to Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli-627 012, Tamil Nadu, India.) E-mail: robinchel@rediffmail.com. 3 Received on July 14, 2022. Accepted on October 15, 2022. Published on January 30, 2023. doi: 10.23755/rm.v45i0.977. ISSN: 1592-7415. eISSN: 2282-8214. Β©The Authors. This paper is published under the CC-BY license agreement. 45 E. Sherin Danie and S. Robinson Chellathurai 1. Introduction Let 𝐺 = (𝑉, 𝐸) be any graph with 𝑛vertices and π‘šedges. For any graph theoretic terminlogies not defined here, refer to the book of Bondy and Murthy [3]. One of the fastest growing areas in graph theory is the study of domination and related subset problems such as independence, covering and matching. By a graph 𝐺, we mean a non- trivial, finite, undirected graph with neither loops nor multiple edges. Two vertices 𝑒and 𝑣are said to be adjacent if 𝑒𝑣is an edge of 𝐺. The open neighbourhood of a vertex 𝑣in a graph 𝐺is defined as the set 𝑁𝐺 (𝑣) = {𝑣 ∈ 𝑉 (𝐺) ∢ 𝑒𝑣 ∈ 𝐸(𝐺)}, while the closed neighbourhood of 𝑣in 𝐺is defined as 𝑁𝐺 [𝑣] = 𝑁𝐺 (𝑣) βˆͺ {𝑣}. For any vertex 𝑣in a graph 𝐺, the number of vertices adjacent to 𝑣is called the degree of v in 𝐺, denoted by 𝑑𝑒𝑔𝐺 (𝑣). If the degree of a vertex is 0, it is called an isolated vertex, while if the degree is 1, it is called an end-vertex. The minimum degree of vertices in 𝐺is defined by 𝛿(𝐺) = π‘šπ‘–π‘›{𝑑𝑒𝑔(𝑣)/𝑣 ∈ 𝑉 (𝐺). The maximum degree of vertices in 𝐺is defined by βˆ†(𝐺) = π‘šπ‘Žπ‘₯{𝑑𝑒𝑔(𝑣)/𝑣 ∈ 𝑉 (𝐺). A vertex 𝑣is called a universal vertex if 𝑑𝑒𝑔𝐺(𝑣) = 𝑛 βˆ’ 1.Two edges are said to adjacent edges if they have a common vertex. For any set 𝑆of vertices of G, the induced subgraph < 𝑆 >is the maximal subgraph of G with vertex set. A subset 𝑆 βŠ† 𝑉 (𝐺) is called a dominating set [3, 6, 7, 8]if every vertex 𝑣 ∈ 𝑉 (𝐺) \ 𝑆is adjacent to a vertex 𝑒 ∈ 𝑆. The domination number, 𝛾(𝐺), of a graph 𝐺denotes the minimum cardinality of such dominating sets of 𝐺. A minimum dominating set of a graph 𝐺is hence often called as a Ξ³-set of 𝐺. A subset 𝑆 βŠ† 𝐸 (𝐺) is called an edge dominating set [1, 2] if every edge𝑓 ∈ 𝐸 (𝐺) \ 𝑆is adjacent to an edgeβ„Ž ∈ 𝑆. The edge domination number, 𝛾𝑒 (𝐺), of a graph 𝐺denotes the minimum cardinality of such edge dominating sets of 𝐺. A minimum edge dominating set of a graph 𝐺is hence often called as a 𝛾𝑒 -set of 𝐺. An edge cover [5] of a graph is a set of edges such that every vertex of the graph is incident to atleast one edge of the set. A minimum edge covering is an edge covering of smallest possible size. The edge covering number𝜌(𝐺) is the size of a minimum edge covering.Given a graph 𝐺 and a collection of subsets of its vertices, a subset of 𝑉(𝐺) is called a transversal of 𝐺 if it intersects each subset of the collection [4]. In this paper, we studied the concept of the edge covering transversal edge domination number of𝐺. 2. On the edge covering transversal edge domination number of a graph Definition 2.1. An edge dominating set which intersects every minimum edge covering set in a graph 𝐺is called an edge covering transversal edge dominating set of 𝐺.The minimum cardinality of an edge covering transversal edge dominating set is called an edge covering transversal edge domination number of 𝐺and is denoted by 𝛾𝑒𝑒𝑐𝑑 (𝐺). Any edge covering transversal edge dominating set of cardinalities𝛾𝑒𝑒𝑐𝑑 (𝐺) is called a 𝛾𝑒𝑒𝑐𝑑-set of 𝐺. 46 On the Edge Covering Transversal Edge Domination in Graphs Example 2.2.For the graph 𝐺given in Fig. 2.1, 𝐷1 = {𝑣2𝑣3, 𝑣4𝑣5} and 𝐷2 = {𝑣2𝑣5, 𝑣3𝑣4} are the only two minimum edge dominating sets of 𝐺. Also,𝑆1 = {𝑣1𝑣5, 𝑣2𝑣3, 𝑣3𝑣4},𝑆2 = {𝑣1𝑣2, 𝑣2𝑣3, 𝑣4𝑣5}, 𝑆3 = {𝑣1𝑣2, 𝑣2𝑣5, 𝑣3𝑣4}, 𝑆4 = {𝑣1𝑣5, 𝑣2𝑣3, 𝑣4𝑣5} are the only 4 minimum edge covering sets of 𝐺. Since 𝐷1 ∩ 𝑆3= Ο• and 𝐷2 ∩ 𝑆4 = πœ™, 𝐷1and 𝐷2are not an edge covering transversal edge dominating sets of G and so 𝛾𝑒𝑒𝑐𝑑 (𝐺) = 3.Now,𝐷3 = {𝑣1𝑣2, 𝑣2𝑣3, 𝑣4𝑣5} is a 𝛾𝑒𝑒𝑐𝑑-set of G, so that 𝛾𝑒𝑒𝑐𝑑 (𝐺) = 3. G Figure 2.1 Theorem 2.3. A set 𝑆of edges of 𝐺 = πΎπ‘Ÿ,π‘Ÿ (π‘Ÿ β‰₯ 2) is a minimum edge covering transversal edge domination of 𝐺if and only if 𝑆consists of 𝑛-independent edges. Proof. Let 𝑆 be any set of π‘Ÿ-independent edges of 𝐺 = πΎπ‘Ÿ,𝑠 (2 ≀ π‘Ÿ ≀ 𝑠). Then S is a minimum edge covering set of 𝐺. Since 𝑆 ∩ 𝐷 = πœ™for any edge covering transversal edge dominating set 𝐷of 𝐺, 𝑆is an edge covering transversal edge dominating set of 𝐺. Hence, it follows that 𝛾𝑒𝑒𝑐𝑑 (𝐺) ≀ π‘Ÿ. If 𝛾𝑒𝑒𝑐𝑑 (𝐺) ≀ π‘Ÿ, then there exists an edge covering transversal edge dominating set 𝑆’, such that |𝑆′| < π‘Ÿ. Therefore, there exists atleast one vertex v of G, such that v is not incident with any edge of 𝑆’ and so 𝑆’ is not an edge covering transversal edge dominating set of 𝐺, which is a contradiction. Hence, S is a minimum edge covering transversal edge dominating set of 𝐺. Conversely, let 𝑆be a minimum edge covering set of G. Let 𝑆’ be any set of nindependent set of edges of 𝐺.Then as in first part of this theorem, 𝑆'β€² is a minimum edge covering set of 𝐺. Therefore, | 𝑆′| = π‘Ÿ. Hence, |𝑆| = π‘Ÿ. If 𝑆is not independent, then there exists a vertex 𝑣of 𝐺such that, 𝑣is not independent with any edge of 𝑆. Hence 𝑆is not an edge covering transversal edge dominating set of G, which is a contradiction. Thus, S consists of r-independent edges. Theorem 2.4. A set S of edges of 𝐺 = πΎπ‘Ÿ,𝑠(2 ≀ π‘Ÿ ≀ 𝑠 ) is a minimum edge covering transversal edge domination of 𝐺, if and only if 𝑆consists of π‘Ÿ βˆ’ 1 independent edges of 𝐺and 𝑠 βˆ’ π‘Ÿ + 1 adjacent edges of𝐺. Proof. Let 𝑋 = {𝑒1, 𝑒2, . . . . . , π‘’π‘Ÿ } and π‘Œ = {𝑣1, 𝑣2, . . . . . , 𝑣𝑠 } be a bipartition of 𝐺. Let 𝑆be any set of π‘Ÿ βˆ’ 1 independent edges of G and 𝑠 βˆ’ π‘Ÿ + 1 adjacent edges of 𝐺.Since each vertex of 𝐺is incident with an edge of 𝑆, it follows that 𝛾𝑒𝑒𝑐𝑑 (𝐺) < 𝑠. v 5 v 2 v 4 v 3 v 1 47 E. Sherin Danie and S. Robinson Chellathurai If 𝛾𝑒𝑒𝑐𝑑 (𝐺) < 𝑠, then there exists an edge covering transversal edge dominating set S β€² of 𝐺such that |𝑆′| < 𝑠. Therefore, there exists atleast one vertex 𝑣of 𝐺such that 𝑣is not incident with any edge of 𝑆′ and so 𝑆′ is not an edge covering transversal edge dominating set of 𝐺, which is a contradiction. Hence, 𝑆is a minimum edge covering transversal edge dominating set of 𝐺. Conversely, let𝑆be a minimum edge covering transversal edge dominating set of 𝐺. Let Sβ€² be any set of π‘Ÿ βˆ’ 1 independent edges of 𝐺and π‘Ÿ βˆ’ 𝑠 + 1 adjacent edges of 𝐺. Then as in the first part of this theorem, 𝑆is a minimum edge covering transversal edge dominating set of 𝐺. Therefore |𝑆′| = 𝑠. Hence |𝑆| = 𝑠. Let us assume that 𝑆 = 𝑆1 βˆͺ 𝑆2, where 𝑆1consists of independent edges and 𝑆2consists of adjacent edges of 𝐺. If |𝑆1| ≀ 𝑠 βˆ’ 2, then 𝑆2must contain atmost edges𝑠 βˆ’ π‘Ÿ. Then there exists atleast one vertex 𝑣of 𝑋, such that 𝑣is not incident with any edge of 𝑆and so 𝑆is not an edge covering transversal edge dominating set of 𝐺, which is a contradiction. Therefore 𝑆consists of 𝑠 βˆ’ 1 independent edges of 𝐺and 𝑠 βˆ’ π‘Ÿ + 1 adjacent edges of 𝐺. Corollary 2.5. For the complete bipartite graph, πΎπ‘Ÿ,𝑠(2 ≀ π‘Ÿ ≀ 𝑠 ), 𝛾𝑒𝑒𝑐𝑑 (𝐺) = 𝑠. Theorem 2.6. For the complete graph 𝐺 = 𝐾𝑛(𝑛 β‰₯ 4) with 𝑛even, a set 𝑆of edges of 𝐺is a minimum edge covering transversal edge domination of 𝐺if and only if 𝑆consists of 𝑛 2 independent edges. Proof. The proof is similar to the proof of the Theorem 2.4. Theorem 2.7. For the complete graph 𝐺 = 𝐾𝑛(𝑛 β‰₯ 5)G with𝑛odd, a set 𝑆of edges of 𝐺is a minimum edge covering transversal edge dominating set of 𝐺if and only if S consists of π‘›βˆ’3 2 independent edges and two adjacent edges of 𝐺. Proof. The proof is similar to the proof of the Theorem 2.4. . Corollary2.8. For the Complete graph 𝐺 = 𝐾𝑛(𝑛 β‰₯ 4), 𝛾𝑒𝑒𝑐𝑑 (𝐺) = { 𝑛 2 if𝑛 is even 𝑛 + 1 2 if 𝑛 is odd Theorem 2.9. For the Cycle 𝐺 = 𝐢𝑛(𝑛 β‰₯ 4), 𝛾𝑒𝑒𝑐𝑑 (𝐺) = { 𝑛 2 if 𝑛 is even ⌈ 𝑛 2 βŒ‰ if 𝑛 is odd Proof. Let 𝐢𝑛: {𝑣1, 𝑣2, 𝑣3, . . . . , 𝑣𝑛 , 𝑣1} be the cycle. We consider the following two cases Case (i). 𝑛is even. Let 𝑛 = 2π‘˜(π‘˜ β‰₯ 2), then 𝑆1 = {𝑣1𝑣2, 𝑣3𝑣4, 𝑣5𝑣6, … , 𝑣2π‘˜βˆ’1𝑣2π‘˜ } and 𝑆2 = {𝑣2𝑣3, 𝑣4𝑣5, 𝑣6𝑣7, … , 𝑣2π‘˜βˆ’2𝑣2π‘˜βˆ’1, 𝑣2π‘˜ 𝑣1}are the only two minimum edge covering sets of 𝐺. Let D be an edge dominating sets of 𝐺. Then it is clear that 𝐷 ∩ 𝑆1 β‰  πœ™and𝐷 ∩ 48 On the Edge Covering Transversal Edge Domination in Graphs 𝑆2 β‰  πœ™. Therefore 𝑆1and 𝑆2are the only two minimum edge covering transversal edge dominating sets of 𝐺, so that𝛾𝑒𝑒𝑐𝑑 (𝐺) = π‘˜ = 𝑛 2 Case (ii). 𝒏 is odd Let. 𝑛 = 2π‘˜ + 1(π‘˜ β‰₯ 2), then𝑆1 = {𝑣1𝑣2, 𝑣3𝑣4, 𝑣5𝑣6, … , 𝑣2π‘˜βˆ’1𝑣2π‘˜ , 𝑣2π‘›π‘˜ 𝑣2π‘˜+1} is a minimum edge covering transversal edge dominating set of 𝐺, so that𝛾𝑒𝑒𝑐𝑑 (𝐺) = ⌈ 𝑛 2 βŒ‰. Theorem 2.10. For the path 𝐺 = 𝑃𝑛 (𝑛 β‰₯ 4), 𝛾𝑒𝑒𝑐𝑑 (𝐺) = { 𝑛 2 if 𝑛 is even 𝑛+1 2 if 𝑛 is odd Proof. The proof is similar to the proof of the Theorem 2.9. Theorem 2.11. For the star graph, 𝐺 = 𝐾1,π‘›βˆ’1, 𝛾𝑒𝑒𝑐𝑑 (𝐺) = 𝑛 βˆ’ 1. Theorem 2.12. For the wheel graph 𝐺 = 𝐾1 + πΆπ‘›βˆ’1(𝑛 β‰₯ 5), 𝛾𝑒𝑒𝑐𝑑 (𝐺) = { 𝑛 βˆ’ 1 2 if 𝑛 βˆ’ 1 𝑖s even 𝑛 + 1 2 if 𝑛 βˆ’ 1 is odd Figure 2.2 Proof.Let𝑉 (𝐾1) = {π‘₯} and πΆπ‘›βˆ’1𝑏𝑒 𝑣1, 𝑣2, 𝑣3, . . . . , π‘£π‘›βˆ’1, 𝑣1. We consider the following cases. Case (i).𝒏 – 𝟏 is even. Let 𝑛 βˆ’ 1 = 2π‘˜(π‘˜ β‰₯ 3). Then 𝑆1 = {𝑣1𝑣2, 𝑣3𝑣4, 𝑣5𝑣6, … , 𝑣2π‘˜βˆ’1𝑣2π‘˜ } and 𝑆2 = {𝑣2𝑣3, 𝑣4𝑣5, 𝑣6𝑣7, … , 𝑣2π‘˜βˆ’2𝑣2π‘˜βˆ’1, 𝑣2π‘˜ 𝑣1}are the only two minimum edge covering sets of 𝐺. Then it is clear that 𝐷 ∩ 𝑆1 β‰  πœ™and that 𝐷 ∩ 𝑆2 β‰  πœ™. Therefore 𝑆1and 𝑆2are the only two minimum edge covering transversal edge dominating sets of 𝐺, so that𝛾𝑒𝑒𝑐𝑑 (𝐺) = π‘˜ = π‘›βˆ’1 2 . v 7 v 1 v 6 v 5 v 2 v 4 v 3 49 E. Sherin Danie and S. Robinson Chellathurai Case (ii). 𝒏 – 𝟏 is odd. Let 𝑛 βˆ’ 1 = 2π‘˜ + 1(π‘˜ β‰₯ 2). Then𝑆1 = {𝑣1𝑣2, 𝑣3𝑣4, 𝑣5𝑣6, … , 𝑣2π‘˜βˆ’1𝑣2π‘˜ , 𝑣2π‘˜ 𝑣2π‘˜+1} is a minimum edge covering transversal edge dominating set of 𝐺, so that 𝛾𝑒𝑒𝑐𝑑 (𝐺) = ⌈ π‘›βˆ’1 2 βŒ‰. Theorem 2.13. Let G be a connected graph withmedges (mβ‰₯ 2), then 1 ≀ Ξ³eect (G) ≀ m. Theorem 2.14. For any graph 𝐺, 𝛾𝑒 (𝐺) ≀ 𝛾𝑒𝑒𝑐𝑑 (𝐺) ≀ 𝛾𝑒 (𝐺) + βˆ†(𝐺). Proof. Let 𝐷be a 𝛾𝑒𝑒𝑐𝑑 t-set of 𝐺. Then 𝐷itself is an edge dominating set. Therefore 𝛾𝑒 (𝐺) ≀ |𝐷| = 𝛾𝑒𝑒𝑐𝑑 (𝐺). Now, let S be a 𝛾𝑒 -set in G and let v be a vertex of maximum degree. Therefore 𝑑𝑒𝑔(𝑣) = βˆ†(𝐺). Then every minimum edge covering transversal edge dominating set of 𝐺contains an edge of < 𝐸[𝑁(𝑣)] > so 𝑆 βˆͺ< 𝐸[𝑁(𝑣)] >is an edge covering transversal edge dominating set. Also, since 𝑆intersects < 𝐸[𝑁(𝑣)] > |𝑆 βˆͺ< 𝐸[𝑁(𝑣)] > | ≀ 𝛾𝑒 (𝐺) + βˆ†(𝐺). Then𝛾𝑒 (𝐺) ≀ 𝛾𝑒𝑒𝑐𝑑 (𝐺) ≀ 𝛾𝑒 (𝐺) + βˆ†(𝐺). Remark 2.15. The bound in the Theorem 2.14 is sharp. Figure 2.3 For the graph given in Figure 2.3,𝑆1 = {𝑣1𝑣2, 𝑣3𝑣4} is a 𝛾𝑒 -set of G and 𝛾𝑒𝑒𝑐𝑑-set of 𝐺so that 𝛾𝑒 (𝐺) = 𝛾𝑒𝑒𝑐𝑑 (𝐺). 3. Conclusions In this paper, we obtain some results related to edge covering transversal domination in graphs and this work gives the scope for an extensive study of various domination parameters of these graphs. Acknowledgment The authors are highly thankful to the anonymous referees for their kind comments and fruitful suggestions on the first draft of this paper. v 4 v 3 v 2 v 1 G 50 On the Edge Covering Transversal Edge Domination in Graphs References [1] Araya Chaemchan, The edge domination number of connected graphs, Australian Journal of Combinatorics, 48, (2010), 185–189 [2] S. Arumugam and S. Velammal, Edge domination in graphs, Taiwanese Journal of Mathematics, 29 (2), (1998), 173–179. [3] J.A. Bondy, U.S.R. Murty, Graph Theory with application, Elsevier Science Publishing Co, Sixth Printing, (1984). [4] Ismail Sahul Hamid, Independent transversal Domination in Graphs, Discussiones Mathematicae, Graph Theory, 32, (2012), 5 βˆ’ 17. [5] J. John, A. Vijayan and S. Sujitha, The forcing edge covering number of a graph Journal of Discrete Mathematical Sciences and Cryptography 14 (3), (2011), 249–259 [6] J. John and V. Sujin Flower, On the forcing domination and forcing total domination number of a graph, Graphs and Combinatorics, 38(5), (2022). https://doi.org/10.1007/s00373-022-02521-y [7] J. John and Malchijah Raj, The forcing non split domination number of a graph, Korean Journal of Mathematics, 29(1),(2021),1–12. [8] S. Kavitha, S.R Chellathurai, J. John, On the forcing connected domination number of a graph, Journal of Discrete Mathematical Sciences and Cryptography, 20 (3), (2017), 611–-624. 51