Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


For citation:

Ganesamoorthy K., Lakshmi Priya S. Forcing total outer connected monophonic number of a graph. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2022, vol. 22, iss. 3, pp. 278-286. DOI: 10.18500/1816-9791-2022-22-3-278-286, EDN: IMTPKR

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
31.08.2022
Full text:
(downloads: 1179)
Language: 
English
Heading: 
Article type: 
Article
UDC: 
519.17
EDN: 
IMTPKR

Forcing total outer connected monophonic number of a graph

Autors: 
Ganesamoorthy Kathiresan, Coimbatore Institute of Technology
Lakshmi Priya Shanmugam, CIT Sandwich Polytechnic College
Abstract: 

For a connected graph $G = (V,E)$ of order at least two, a subset $T$ of a minimum total outer connected monophonic set $S$ of $G$ is a forcing total outer connected monophonic subset for $S$ if $S$ is the unique minimum total outer connected monophonic set containing $T$. A forcing total outer connected monophonic subset for $S$ of minimum cardinality is a minimum forcing total outer connected monophonic subset of $S$. The forcing total outer connected monophonic number $f_{tom}(S)$ in $G$ is the cardinality of a minimum forcing total outer connected monophonic subset of $S$. The forcing total outer connected monophonic number of $G$ is $f_{tom}(G) =  \min\{f_{tom}(S)\}$, where the minimum is taken over all minimum total outer connected monophonic sets $S$ in $G$.  We determine bounds for it and find the forcing total outer connected monophonic number of a certain class of graphs.  It is shown that for every pair $a,b$ of positive integers with $0 \leq a < b$ and $b \geq a+4$, there exists a connected graph $G$ such that $f_{tom}(G) = a$ and $cm_{to}(G) = b$, where $cm_{to}(G)$ is the total outer connected monophonic number of a graph.

Acknowledgments: 
The first author's research work was supported by National Board for Higher Mathematics (NBHM), Department of Atomic Energy (DAE), Government of India (project No. NBHM/R.P.29/2015/Fresh/157).
References: 
  1. Buckley F., Harary F. Distance in Graphs. Redwood City, CA, Addison-Wesley, 1990. 335 p.
  2. Harary F. Graph Theory. Addision-Wesley, 1969. 274 p.
  3. Costa E. R., Dourado M. C., Sampaio R. M. Inapproximability results related to monophonic convexity. Discrete Applied Mathematics, 2015, vol. 197, pp. 70–74. https://doi.org/10.1016/j.dam.2014.09.012
  4. Dourado M. C., Protti F., Szwarcfiter J. L. Algorithmic aspects of monophonic convexity. Electronic Notes in Discrete Mathematics, 2008, vol. 30, pp. 177–182. https://doi.org/10.1016/j.endm.2008.01.031
  5. Dourado M. C., Protti F., Szwarcfiter J. L. Complexity results related to monophonic convexity. Discrete Applied Mathematics, 2010, vol. 158, pp. 1268–1274. https://doi.org/10.1016/j.dam.2009.11.016
  6. Paluga E. M., Canoy S. R. Monophonic numbers of the join and composition of connected graphs. Discrete Mathematics, 2007, vol. 307, iss. 9–10, pp. 1146–1154. https://doi.org/10.1016/j.disc.2006.08.002  
  7. Santhakumaran A. P., Titus P., Ganesamoorthy K. On the monophonic number of a graph. Journal of Applied Mathematics & Informatics, 2014, vol. 32, iss. 1–2, pp. 255–266. https://doi.org/10.14317/JAMI.2014.255
  8. Ganesamoorthy K., Murugan M., Santhakumaran A. P. Extreme-support total monophonic graphs. Bulletin of the Iranian Mathematical Society, 2021, vol. 47, pp. 159–170. https://doi.org/10.1007/s41980-020-00485-4
  9. Ganesamoorthy K., Murugan M., Santhakumaran A. P. On the connected monophonic number of a graph. International Journal of Computer Mathematics: Computer Systems Theory, 2022, vol. 7, iss. 2, pp. 139–148. https://doi.org/10.1080/23799927.2022.2071765
  10. Santhakumaran A. P., Titus P., Ganesamoorthy K., Murugan M. The forcing total monophonic number of a graph. Proyecciones, 2021, vol. 40, iss. 2, pp. 561–571. https://doi.org/10.22199/issn.0717-6279-2021-02-0031
  11. Ganesamoorthy K., Lakshmi Priya S. The outer connected monophonic number of a graph. Ars Combinatoria, 2020, vol. 153, pp. 149–160.
  12. Ganesamoorthy K., Lakshmi Priya S. 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, Issue Mathematics, 2021, vol. 41, iss. 4, pp. 51–59.
  13. Ganesamoorthy K., Lakshmi Priya S. Extreme outer connected monophonic graphs. Communications in Combinatorics and Optimization, 2022, vol. 7, iss. 2, pp. 211–226. https://dx.doi.org/10.22049/cco.2021.27042.1184
Received: 
15.09.2021
Accepted: 
12.12.2021
Published: 
31.08.2022