On the Total Monophonic Number of a Graph

Document Type : Special Issue for ICGCO-2022


1 Director (n-CARDMATH) Kalasalingam University Anand Nagar, Krishnankoil-626 126 Tamil Nadu, India

2 Department of Mathematics Hindustan Institute of Technology and Science Chennai - 603 103, India

3 Department of Mathematics, University College of Engineering, Nagercoil

4 Department of Mathematics, Coimbatore Institute of Technology (Government Aided Autonomous Institution) Coimbatore - 641 014, India

5 Mathematics, Coimbatore Institute of Technology, Coimbatore - 14


Let G = (V,E) be a connected graph of order n. A path P in G which does not have a chord is called a monophonic path. A subset S of V is called a monophonic set if every vertex v in V lies in a x-y monophonic path where x, y 2 S. If further the induced subgraph G[S] has no isolated vertices, then S is called a total monophonic set. The total monophonic number mt(G) and the upper total monophonic number m+t (G) are respectively the minimum cardinality of a total monophonic set and the maximum cardinality of a minimal total monophonic set. In this paper we determine the value of these parameters for some classes of graphs and establish bounds for the same. We also prove the existence of graphs with prescribed values for mt(G) and m+t (G).


Main Subjects

[1] H. Abdollahzadeh Ahangar and V. Samodivkin, The total geodetic number of a graph, Util. Math. 100 (2016), 253–268.
[2] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley Redwood City, 1990.
[3] G. Chartrand, F. Harary, H.C. Swart, and P. Zhang, Geodomination in graphs, Bulletin of the ICA 31 (2001), 51–59.
[4] G. Chartrand, F. Harary, and P. Zhang, On the geodetic number of a graph, Networks 39 (2002), no. 1, 1–6.
[5] G. Chartrand, G.L. Johns, and P. Zhang, On the detour number and geodetic number of a graph, Ars Combin. 72 (2004), 3–15.
[6] K. Ganesamoorthy, M. Murugan, and A.P. Santhakumaran, Extreme-support total monophonic graphs, Bull. Iran. Math. Soc. 47 (2021), no. 1, 159–170.
[7] K. Ganesamoorthy, M. Murugan, and A.P. Santhakumaran, On the connected monophonic number of a graph, Int. J. Comput. Math.: Computer Systems Theory 7 (2022), no. 2, 139–148.
[8] K. Ganesamoorthy, M. Murugan, A.P. Santhakumaran, and P. Titus, The total monophonic number of a graph, (submitted).
[9] F. Harary, E. Loukakis, and C. Tsouros, The geodetic number of a graph, Math. Comput. Modelling 17 (1993), no. 11, 89–95.
[10] Ganesamoorthy K. and S. Lakshmi Priya, Extreme outer connected monophonic graphs, Commun. Comb. Optim. 7 (2022), no. 2, 211–226.
[11] L. Lesniak and G. Chartrand, Graphs & Digraphs, CRC, Boca Raton, 2016.
[12] R. Muntean and P. Zhang, On geodomination in graphs, Congr. Numer. 143 (2000), 161–174.
[13] V. Samodivkin, On the edge geodetic and edge geodetic domination numbers of a graph, Commun. Comb. Optim. 5 (2020), no. 1, 41–54.
[14] A.P. Santhakumaran, P. Titus, and K. Ganesamoorthy, On the monophonic number of a graph, J. Appl. Math. & Informatics 32 (2014), no. 1 2, 255–266.
[15] A.P. Santhakumaran, P. Titus, K. Ganesamoorthy, and M. Murugan, The forcing total monophonic number of a graph, Proyecciones 40 (2021), no. 2, 561–571.