Minimal connected restrained monophonic sets in graphs

Authors

  • A. P. Santhakumaran Hindustan Institute of Technology and Science.
  • P. Titus University College of Engineering Nagercoil.
  • K. Ganesamoorthy Coimbatore Institute of Technology.

DOI:

https://doi.org/10.22199/issn.0717-6279-4475

Keywords:

restrained monophonic set, restrained monophonic number, connected restrained monophonic set, connected restrained monophonic number, minimal connected restrained monophonic set

Abstract

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. 

Author Biographies

A. P. Santhakumaran, Hindustan Institute of Technology and Science.

Department of Mathematics.

P. Titus, University College of Engineering Nagercoil.

Department of Mathematics.

K. Ganesamoorthy, Coimbatore Institute of Technology.

Department of Mathematics.

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

2022-07-26

How to Cite

[1]
A. P. Santhakumaran, P. Titus, and K. Ganesamoorthy, “Minimal connected restrained monophonic sets in graphs”, Proyecciones (Antofagasta, On line), vol. 41, no. 4, pp. 879-890, Jul. 2022.

Issue

Section

Artículos

Most read articles by the same author(s)

1 2 > >>