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

International Journal of Mathematical Trends and Technology (IJMTT)  
© 2012 by IJMTT Journal  
Volume3 Issue1 

Year of Publication : 2012  
Authors : J. John, P. Arul Paul Sudhahar 
J. John, P. Arul Paul Sudhahar "The Upper Connected Monophonic Number and Forcing Connected Monophonic Number of a Graph"International Journal of Mathematical Trends and Technology (IJMTT),V3(1):2933.June 2012. Published by Seventh Sense Research Group.
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.
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) 1726.
[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), 4652.
[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) 1771822.
[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), 15711580.
[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.
Keywords
monophonic number, connected monophonic number, upper connected monophonic number, forcing connected monophonic number.