Minimal connected restrained monophonic sets in graphs
DOI:
https://doi.org/10.22199/issn.0717-6279-4475Keywords:
restrained monophonic set, restrained monophonic number, connected restrained monophonic set, connected restrained monophonic number, minimal connected restrained monophonic setAbstract
For a connected graph G = (V,E) of order at least two, a connected restrained monophonic set S of G is a restrained monophonic set such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected restrained monophonic set of G is the connected restrained monophonic number of G and is denoted by mcr(G). A connected restrained monophonic set S of G is called a minimal connected restrained monophonic set if no proper subset of S is a connected restrained monophonic set of G. The upper connected restrained monophonic number of G, denoted by m+cr(G), is defined as the maximum cardinality of a minimal connected restrained monophonic set of G. We determine bounds for it and certain general properties satisfied by this parameter are studied. It is shown that, for positive integers a, b such that 4≤ a ≤ b , there exists a connected graph G such that mcr(G) = a and m+cr(G) = b.
References
F. Buckley and F. Harary, Distance in Graphs. Redwood City, CA: Addison-Wesley, 1990.
E. R. Costa, M. C. Dourado, and R. M. Sampaio, “Inapproximability results related to monophonic convexity”, Discrete Applied Mathematics, vol. 197, pp. 70–74, 2015. doi: 10.1016/j.dam.2014.09.012
M. C. Dourado, F. Protti, and J. L. Szwarcfiter, “Algorithmic aspects of monophonic convexity”, Electronic Notes in Discrete Mathematics, vol. 30, pp. 177–182, 2008. doi: 10.1016/j.endm.2008.01.031
M. C. Dourado, F. Protti, and J. L. Szwarcfiter, “Complexity results related to monophonic convexity”, Discrete Applied Mathematics, vol. 158, no. 12, pp. 1268–1274, 2010. doi: 10.1016/j.dam.2009.11.016
K. Ganesamoorthy and S. Lakshmi Priya, “The Outer Connected Monophonic Number of a Graph”, Ars Combinatoria, vol. 153, pp. 149-160, 2020.
K. Ganesamoorthy and S. Lakshmi Priya, “Extreme Outer Connected Monophonic Graphs”, Communications in Combinatorics and Optimization, 2021, doi: 10.22049/CCO.2021.27042.1184
K. Ganesamoorthy and S. Lakshmi Priya, “Further results on the outer connected monophonic number of a graph”, Transactions of National Academy of Sciences of Azerbaijan. Series of Physical-Technical and Mathematical Sciences, vol. 41, no. 4, pp. 51-59, 2021. [On line]. Available: https://bit.ly/3J2aABI
K. Ganesamoorthy, M. Murugan, and A. P. N. Santhakumaran, “Extreme-support total monophonic graphs”, Bulletin of the Iranian Mathematical Society, vol. 47, no. S1, pp. 159–170, 2021. doi: 10.1007/s41980-020-00485-4
F. Harary, Graph Theory. Addison-Wesley, 1969.
E. M. Paluga and S. R. Canoy, Jr, “Monophonic numbers of the join and composition of connected graphs”, Discrete Mathematics, vol. 307, no. 9-10, pp. 1146–1154, 2007. doi: 10.1016/j.disc.2006.08.002
A. P. Santhakumaran and P. Titus, “Monophonic Distance in Graphs”, Discrete Mathematics, Algorithms and Applications, vol. 3, no. 2, pp. 159-169, 2011. doi: 10.1142/s1793830911001176
A. P. Santhakumaran and P. Titus, A Note on “Monophonic Distance in Graphs”, Discrete Mathematics, Algorithms and Applications, vol. 4, no. 2, 2012, doi: 10.1142/S1793830912500188
A. P. Santhakumaran, P. Titus and K. Ganesamoorthy, “On the Monophonic Number of a Graph”, Journal of applied mathematics & informatics, vol. 32, no. 1-2, pp. 255-266, 2014. doi: 10.14317/jami.2014.255
A. P. Santhakumaran, P. Titus and K. Ganesamoorthy, “The Restrained Monophonic Number of a Graph”, TWMS journal of pure and applied mathematics (Online). Accepted.
A. P. Santhakumaran, P. Titus and K. Ganesamoorthy, “The Connected and Forcing Connected Restrained Monophonic Numbers of a Graph”, Communicated.
A. P. Santhakumaran, P. Titus, K. Ganesamoorthy, and M. Murugan, “The forcing total monophonic number of a graph”, Proyecciones (Antofagasta), vol. 40, no. 2, pp. 561–571, 2021. doi: 10.22199/issn.0717-6279-2021-02-0031
A. P. Santhakumaran, T. Venkata Raghu and K. Ganesamoorthy, “Minimal Restrained Monophonic Sets in Graphs”, TWMS journal of pure and applied mathematics (Online), vol. 11, no. 3, pp. 762-771, 2021.
Published
How to Cite
Issue
Section
Copyright (c) 2022 A. P. Santhakumaran, P. Titus, K. Ganesamoorthy
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.