The forcing monophonic and forcing geodetic numbers of a graph
Abstract
For a connected graph G = (V, E), let a set S be a m-set of G. A subset T ⊆ S is called a forcing subset for S if S is the unique m-set containing T. A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing monophonic number of S, denoted by fm(S), is the cardinality of a minimum forcing subset of S. The forcing monophonic number of G, denoted by fm(G), is fm(G) = min{fm(S)}, where the minimum is taken over all minimum monophonic sets in G. We know that m(G) ≤ g(G), where m(G) and g(G) are monophonic number and geodetic number of a connected graph G respectively. However there is no relationship between fm(G) and fg(G), where fg(G) is the forcing geodetic number of a connected graph G. We give a series of realization results for various possibilities of these four parameters.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.19184/ijc.2020.4.2.5
References
H.A. Ahangara, S. Kosarib, S.M. Sheikholeslamib, and L. Volkmannc, Graphs with large geodetic number, Filomat. 29:6 (2015), 1361 – 1368.
F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, Redwood City, CA, 1990.
J. Caceres, O. Oellermann, and M. Puertasa, Minimal trees and monophonic convexity, Discuss. Math. Graph Theory, 32, (2012), 685 – 704.
G. Chartrand and P. Zhang, The forcing geodetic number of a graph, Discuss. Math. Graph Theory, 19, (1999), 45 – 58.
G. Chartrand, F. Harary, and P. Zhang, On the geodetic number of a graph, Networks, (2002), 1 – 6.
M.C. Dourado, F. Protti, D. Rautenbach, and J.L. Szwarcfiter, Some remarks on the geodetic number of a graph, Discrete Math. 310, (2010), 832 – 837.
M.C. Dourado, F. Protti, and J.L. Szwarcfiter, Algorithmic aspects of monophonic convexity, Electron. Notes Discrete Math. 30, (2008), 177 – 182.
F. Harary, E. Loukakis, and C. Tsouros, The geodetic number of a graph, Math. Comput. Modeling, 17(11), (1993), 89 – 95.
C. Hernando, T. Jiang, M. Mora, I.M. Pelayo, and C. Seara, On the Steiner, geodetic and hull number of graphs, Discrete Math. 293, (2005), 139 – 154.
J. John and P.A.P. Sudhahar, The forcing edge monophonic number of a graph , SCIENTIA Series A: Mathematical Sciences, 23, (2012), 87-98
J. John and S. Panchali, The forcing monophonic number of a graph, IJMA-3 (3), (2012), 935–938.
J. John and S. Panchali, The upper monophonic number of a graph, Int. J. Math. Combin. 4, (2010), 46 – 52
J. John and K.U. Samundeswari, The forcing edge fixing edge-to-vertex monophonic number of a graph, Discrete Math. Algorithms Appl. 5(4), (2013), 1 – 10.
J. John and K.U. Samundeswari, The edge fixing edge-to-vertex monophonic number of a graph, Appl. Math. E-Notes. 15, (2015), 261 – 275.
J. John and K.U. Samundeswari, Total and forcing total edge-to-vertex monophonic numbers of graph, J. Comb. Optim. 34, (2017), 1 – 14.
J. John and D. Stalin, Edge geodetic self decomposition in graphs, Discrete Math. Algorithms Appl. 12(5), (2020), 2050064, 7 pages.
J. John and D. Stalin,The edge geodetic self decomposition number of a graph, RAIRO Oper. Res. , DOI:10.1051/ro/2020073.
J. John and D. Stalin, Distinct edge geodetic decomposition in graphs, Commun. Comb. Optim., DOI: 10.22049/CCO.2020.26638.1126
E.M. Paluga and S.R. Canoy, Jr, Monophonic numbers of the join and composition of connected graphs, Discrete Math. 307, (2007), 1146 – 1154.
I.M. Pelayo, Geodesic Convexity in Graphs, Springer Briefs in Mathematics, 2013.
A.P. Santhakumaran and J. John, On the forcing geodetic and forcing Steiner numbers of a graph, Discuss. Math. Graph Theory. 31, (2011), 611 – 624.
Li-Da Tong, Geodetic sets and Steiner sets in graphs, Discrete Math. 309(12), (2009), 3733–4214.
Li-Da Tong, The forcing hull and forcing geodetic numbers of graphs, Discrete Appl. Math. 157(5), (2009), 875 – 1164.
Li-Da Tong, The (a,b)-forcing geodetic graphs, Discrete Math. 309(6), (2009), 1199 – 1792.
P. Zhang, The upper forcing geodetic number of a graph, Ars Combin., DOI: 10.7151/dmgt.1084.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.