Ratio Mathematica Volume 44, 2022 On The Study of Edge Monophonic Vertex Covering Number K. A. Francis Jude Shini* S. Durai Raj† X. Lenin Xaviour‡ A. M. Anto§ Abstract For a connected graph G of order n ≥ 2, a set S of vertices of G is an edge monophonic vertex cover of G if S is both an edge monophonic set and a vertex covering set of G. The minimum cardinality of an edge monophonic vertex cover of G is called the edge monophonic vertex covering number of G and is denoted by 𝒎𝒆𝜶(𝑮). Any edge monophonic vertex cover of cardinality 𝒎𝒆𝜶(𝑮) is a 𝒎𝒆𝜶(𝑮)-set of G. Some general properties satisfied by edge monophonic vertex cover are studied. Keywords: monophonic set; edge monophonic set; vertex coveringset; edgemonophonic vertex cover; edge monophonic vertex covering number. 2010 AMS subject classification: 05C12**. *Research Scholar, Reg No: 20213132092001, Department of Mathematics, (Pioneer Kumaraswamy College, Nagercoil-629003, Tamil Nadu, India.); shinishini111@gmail.com †Associate Professor and Principal, Department of Mathematics, (Pioneer Kumaraswamy College, Nagercoil-629003, Tamil Nadu, India.); durairajsprinc@gmail.com ‡Assistant Professor, Department of Mathematics, (Nesamony Memorial Christian College, Marthandam- 629165, Tamil Nadu, India.); leninxaviour93@gmail.com §Assistant Professor, Department of Mathematics, (St. Alberts College(Autonomous), Ernakulam, Kochi, India.); antoalexam@gmail.comAffiliated to ManonmaniamSundaranar University, Abishekapatti, Tirunelveli – 627 012, TamilNadu, India. ** Received on June 10 th, 2022. Accepted on Sep 1st, 2022. Published on Nov30th, 2022. doi: 10.23755/rm.v44i0.907. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors.This paper is published under the CC-BY licence agreement. 197 mailto:shinishini111@gmail.com mailto:durairajsprinc@gmail.com mailto:leninxaviour93@gmail.com mailto:antoalexam@gmail.com K. A. Francis Jude Shini, S. Durai Raj, X. Lenin Xaviour and A. M. Anto 1. Introduction By a graph G=(V,E) , we mean a finite undirected connected graph without loops and multiple edges. The order and size of G are denoted by n and m respectively. Also 𝛿(𝐺) is the minimum degree in a graph G. For basic graph theoretic terminology, we refer to Harary[7]. The distance d(u,v) between two vertices u and v in a connected graph G is the length of a shortest u-v path in G(1) For a vertex v of G, the eccentricity e(v) is the distance between v and a vertex farthest fromv. The minimum eccentricity among the vertices of G is the radius, rad G and the maximum eccentricity is its diameter, diamG. The neighbourhood of a vertex v of G is the set N(v) consisting of all vertices which are adjacent with v. A vertex v is a simplicial vertex or an extreme vertex of G if the subgraph induced by its neighbourhood N(v) is complete. A caterpillar is a tree of order 3 or more, the removal of whose end vertices produces a path called the spine of the caterpillar. A diametralpath of a graph is a shortest path whose length is equal to the diameter of the graph. A tree containing exactly two non-pendent vertices is called a doublestar denoted by 𝑆𝐾1𝑘2 where 𝑘1 and 𝑘2 are the number of pendent vertices on these two non-pendent vertices. A graph G is called triangle free if it does not contain cycles of length 3. A set of vertices no two of which are adjacent is called an independentset. By a matching in a graph G, we mean an independent set of edges of G. A maximalmatching is a matching M of a graph G that is not a subset of any other matching. The independencenumber of is the maximum number of vertices in an independent set of vertices of G. A geodeticset of is a set (G) such that every vertex of is contained in a geodesic joining some pair of vertices in S. The geodeticnumber of is the minimum cardinality of its geodetic sets and any geodetic set of cardinalities is a minimumgeodeticset or a geodeticbasis or a -set of G. The geodetic number of a graph was introduced in [2, 8] and further studied in [3-5]. A chord of a path is an edge joining two non-adjacent vertices of P. A path is called a monophonic path if it is a chordless path. A set of vertices of is a monophonic set of if each vertex of lies on an monophonic path for some . The minimum cardinality of a monophonic set of is the monophonicnumber of and is denoted by . Any monophonic set of cardinalities is a minimummonophonicsetoramonophonicbasisora -set of G. The monophonic number of a graph was studied and discussed in [9, 12]. A set of vertices in is called an edgemonophonicset of if every edge of lies on a monophonic path joining some pair of vertices in and the minimum cardinality of an edge monophonic set is the edgemonophonicnumber of G. An edge monophonic set of cardinalities is called an -set of G. The edge monophonic number of a graph was introduced in and further studied in [10]. A subset is said to be a vertexcoveringset of if every edge has at least one end vertex in S. A vertex covering set of with the minimum cardinality is called a 198 On The Study of Edge Monophonic Vertex Covering Number minimumvertexcoveringset of G. The vertexcoveringnumber of is the cardinality of any minimum vertexcovering set of G. It is denoted by vertex covering number was studied in [14]. For a connected graph of order , a set of vertices of is anmonophonicvertexcover of if is both a monophonic set and a vertex covering set of G. The minimum cardinality of ae monophonic vertex cover of is called the monophonicvertexcoveringnumber of and is denoted by . Any monophonic vertex cover of cardinality is a -set of G. A subset is a dominatingset if every vertex in V-S is adjacent to at least one vertex in S. The minimum cardinality of a dominating set in a graph is called the dominating umber of and denoted by . The dominating number of a graph was studied in [6]. A set of vertices of is said to be monophonicdominationset if it is both a monophonic set and a dominating set of G. The minimum cardinality of a monophonic domination set of is called a monophonicdominationnumber of and denoted by . The monophonic domination number was studied in [11]. A set of vertices of a graph is an edgemonophonicdominationset if it is both edge monophonic set and a domination set of G. The minimum cardinality of an edge monophonic domination set of is called an edgemonophonicdominationnumber of and denoted by . The edge monophonic domination number was studied in [13]. The following theorems will be used in the sequel. Theorem 1.1. [10] Every extreme vertex of a connected graph belongs to every edge monophonic set of G. In particular, each end vertex of belongs to every edge monophonic set of G. Theorem 1.2. [10] Let be a connected graph with cut-vertices and be an edge monophonic set of G. If is a cut-vertex of , then every component of G-v contains an element of S. 2.The Edge Monophonic Vertex Coverofa Graph Definition 2.1. Let be a connected graph of order 2. Aset of vertices of is an edgemonophonicvertexcover of if is both an edge monophonic set and a vertex cover of G. The minimum cardinality of an edge monophonic vertex cover of is called the edgemonophonicvertexcoveringnumber of and is denoted by . Any edge monophonic vertex cover of cardinality is a -set of G. Example 2.2. For the graph given in Figure 2.1, is a minimum edge monophonic set of so that and is a minimum edge monophonic vertex cover of so that . Thus, the edge monophonic number and the edge monophonic vertex covering number of a graph are different. 199 K. A. Francis Jude Shini, S. Durai Raj, X. Lenin Xaviour and A. M. Anto Figure 2.1: Remark 2.3. For the graph given in Figure 2.2, is a minimum monophonic vertex cover of so that and is a minimum edge monophonic vertex cover of so that . Hence the monophonic vertex covering number is different from the edge monophonic vertex covering number of a graph. Figure 2.2: Remark 2.4. For the graph given in Figure 2.3, is a minimum edge monophonic set of so that is a minimum edge monophonic dominating set of so that and is a minimum edge monophonic vertex cover of so that . Hence the edge monophonic vertex covering number of a graph is different from the edge monophonic number and the edge monophonic dominating number of a graph. Figure 2.3: 200 On The Study of Edge Monophonic Vertex Covering Number Theorem 2.5. For any connected graph Proof. Any edge monophonic set of needs at least 2 vertices and so . From the definition of edge monophonic vertex cover of , we have, . Clearly V(G) is an edge monophonic vertex cover of G. Hence . Thus Remark 2.6. The bounds in Theorem 2.5 are sharp. For the complete graph . In Remark 2.3, we have, The bounds are strict in Example 2.2 as Here 2 Remark 2.7. Clearly union of a vertex covering set and an edge monophonic set of is an edge monophonic vertex cover of G. In Figure 2.1, is an edge monophonic vertex cover, in Figure 2.2, is an edge monophonic vertex cover and in Figure 2.3, is an edge monophonic vertex cover. Thus Figure 2.4: For the graph in Figure 2.4, we observe that is a minimum vertex cover of so that is a minimum edge monophonic set of so that and is a -set of and so Theorem 2.8. Each extreme vertex of belongs to every edge monophonic vertex cover of G. In particular, each end vertex of belongs to every edge monophonic vertex cover of G. Proof. From the definition of -set, every -set of is a -set of G. Hence the result follows from Theorem 1.1. Corollary 2.9. For any graph with extreme vertices, max{2, } Proof. The result follows from Theorem 2.5 and Theorem 2.8. Corollary 2.10. Let be a star. Then 201 K. A. Francis Jude Shini, S. Durai Raj, X. Lenin Xaviour and A. M. Anto Proof. Let be the centre and be the set of all extreme vertices of . Clearly is a minimum edge monophonic vertex cover of by Theorem 2.8. Hence Corollary 2.11. For the complete graph Proof. Since every vertex of the complete graph is an extreme vertex, by Theorem 2.8, the vertex set is the unique edge monophonic vertex cover of . Thus Remark 2.12. The converse of Corollary 2.11 need not be true. For the graph given in Figure 2.5, is an -set of so that and is not complete. Figure 2.5: Theorem 2.13. Let be a connected graph with cut-vertices and be an edge monophonic vertex cover of G. If is a cut-vertex of , then every component of G-v contains an element of S. Proof. From the definition of -set, every -set of is a -set of G. Hence the result follows from Theorem 1.2. Remark 2.14. The cut-vertex of in Theorem 2.13 need not belong to S. For the graph given in Figure 2.6, is aa edge monophonic vertex cover of G. Here 4 is a cut-vertex which does not belong to and 3 is a cut-vertex which belong to S. Figure 2.6: 202 On The Study of Edge Monophonic Vertex Covering Number Theorem 2.15. If a and are positive integers such that , then there exists a connected graph of order with Proof. We prove this theorem by considering two cases. Case (i): . Let . Then by Theorem 2.11, Case (ii): . Consider , the complete graph on a-l vertices …, . Add new vertices ... to by joining the vertices …, to both and and the graph is shown in Figure 2.7. Let be the set of all extreme vertices of G. Then by Theorem 1.1, they must belong to every edge monophonic set. Also, we observe that is a minimum edge monophonic set. Also the edges of and the edges are covered by the vertices of ’. Now to cover the edges , we must include at least the vertex to . Hence is a minimum edge monophonic vertex cover of G. Thus Figure 2.7: 3.Conclusions In this paper we analysed the edge monophonic vertex covering number of a graph. It is more interesting to continue my research in this area and it is very useful for further research. Acknowledgements The authors are grateful to the reviewers for their valuable remarks to improve this paper. 203 K. A. Francis Jude Shini, S. Durai Raj, X. Lenin Xaviour and A. M. Anto References [1] F. Buckley and F. Harary. Distanceingraphs. Addison‐Wesley, 1990. [2] F. Buckley, F. Harary, and L. Quintas. Extremal results on the geodetic number of a graph.ScientiaA, 2, 1988. [3] G. Chartrand, F. Harary, and P. Zhang. On the geodetic number of a graph. Networks: AnInternationalJournal, , 2002. [4] G. Chartrand, G. L. Johns, and P. Zhang. On the detour number and geodetic number of a graph. ArsCombinatoria, 72:3-15, 2004. [5] G. Chartrand, E. M. Palmer, and P. Zhang. The geodetic number of a graph: A survey. Congressusnumeration, pages 37-58, 2002. [6] A. Hansberg and L. Volkmann. On the geodetic and geodetic domination numbers of a graph. Discretemathematics, , 2010. [7] F. Harary. Graph theory. Addison Wesley publishing company. Reading, MA, USA., 1969. [8] F. Harary, E. Loukakis, and C. Tsouros. The geodetic number of a graph. MathematicalandComputer Modelling, , 1993. [9] J. John and S. Panchali. The upper monophonic number of a graph. InternationalJ. Math. Combin, 4:46-52, 2010. [10] J. John and P. A. P. Sudhahar. On the edge monophonic number of a graph. Filomat, 26(6):1081‐1089, 2012. [11] J. John, P. A. Paul Sudhahar, and D. Stalin. On the number of a graph. Proyecciones(Antofagasta), , 2019. [12] A. Santhakumaran, P. Titus, and K. Ganesamoorthy. On the monophonic number of a graph. Journalofappliedmathematics&informatics, , 2014. [13] P. A. P. Sudhahar, M. M. A. Khayyoom, and A. Sadiquali. Edge monophonic domination number of graphs. J. . InMathematics, , 2016. [14] D. Thakkar and J. Bosamiya. Vertex covering number of a graph. MathematicsToday, 27:30- 35, 2011. 204