The Upper Connected Monophonic Number and Forcing Connected Monophonic Number of a Graph

J. John; P. Arul Paul Sudhahar

doi:https://doi.org/10.14445/22315373/IJMTT-V3I1P505

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 3 | Issue 1 | Year 2012 | Article Id. IJMTT-V3I1P505 | DOI : https://doi.org/10.14445/22315373/IJMTT-V3I1P505

The Upper Connected Monophonic Number and Forcing Connected Monophonic Number of a Graph

J. John, P. Arul Paul Sudhahar

Citation :

J. John, P. Arul Paul Sudhahar, "The Upper Connected Monophonic Number and Forcing Connected Monophonic Number of a Graph," International Journal of Mathematics Trends and Technology (IJMTT), vol. 3, no. 1, pp. 29-33, 2012. Crossref, https://doi.org/10.14445/22315373/IJMTT-V3I1P505

Abstract

A connected monophonic set ࡹ in a connected graph ࡳ = (ࢂ,ࡱ) is called a minimal connected monophonic set if no proper subset of M is a connected monophonic set of ࡳ. The upper connected monophonic number mc + (G) is the maximum cardinality of a minimal connected monophonic set of G. Connected graphs of order p with upper connected monophonic number 2 and p are characterized. It is shown that for any positive integers 2 ≤ a < b ≤ c, there exists a connected graph G with m(G) =a, mc (G) = b and mc + (G) = c, where m(G) is the monophonic number and mc(G) is the connected monophonic number of a graph G. Let M be a minimum connected monophonic set of G. A subset T ⊆ M is called a forcing subset for M if M is the unique minimum connected monophonic set containing T. A forcing subset for M of minimum cardinality is a minimum forcing subset of M. The forcing connected monophonic number of M, denoted by fmc(M), is the cardinality of a minimum forcing subset of M. The forcing connected monophonic number of G, denoted by fmc(G), is fmc(G) = min{fmc(M)}, where the minimum is taken over all minimum connected monophonic set M in G. It is shown that for every integers a and b with a < b, and ࢈ − ૛ࢇ − ૛ > 0, there exists a connected graph G such that, fmc(G) = a and mc (G) = b.

Keywords

monophonic number, connected monophonic number, upper connected monophonic number, forcing connected monophonic number.

References

[1] F. Buckley and F. Harary, Distance in Graphs, Addition- Wesley, Redwood City, CA, 1990.
[2] F. Buckley, F. Harary, L. V. Quintas, Extremal results on the geodetic number of a graph, Scientia A2 (1988) 17-26.
[3] G. Chartrand, F. Harary, Zhang, On the Geodetic Number of a graph, Networks vol. 39(1), (2002) 1 – 6 .
[4] Carmen Hernando, Tao Jiang, Merce Mora, Ignacio. M. Pelayo and Carlos Seara, On the Steiner, geodetic and hull number of graphs, Discrete Mathematics 293 (2005) 139 - 154.
[5] Esamel M. paluga, Sergio R. Canoy, Jr. , Monophonic numbers of the join and Composition of connected graphs, Discrete Mathematics 307 (2007) 1146 - 1154.
[6] J. John and S. Panchali, The upper monophonic number of a graph, International J. math. Combin. 4(2010), 46-52.
[7] J. John and P. Arul Paul Sudhahar, On the edge monophonic number of a graph, (submitted)
[8] J. John and P. Arul Paul Sudhahar, The connected monophonic number of a graph, International Journal of Combinatorial Graph Theory and Applications (in Press).
[9] Mitre C. Dourado, Fabio protti and Jayme. L. Szwarcfiter, Algorithmic Aspects of Monophonic Convexity, Electronic Notes in Discrete Mathematics 30(2008) 177-1822.
[10] A.P. Santhakumaran, P.Titus and J.John, The upper Connected Geodetic Number and Forcing Connected Geodetic Number of a Graph, Discrete Applied Mathematics, 157(2009), 1571-1580.
[11] A.P. Santhakumaran, P.Titus and J.John, On the Connected Geodetic Number of a graph, J.Combin.Math.Combin.Comput, 69(2009) 219- 229.