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
Forcing total outer connected monophonic number of a graph
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.
- Buckley F., Harary F. Distance in Graphs. Redwood City, CA, Addison-Wesley, 1990. 335 p.
- Harary F. Graph Theory. Addision-Wesley, 1969. 274 p.
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Ganesamoorthy K., Lakshmi Priya S. The outer connected monophonic number of a graph. Ars Combinatoria, 2020, vol. 153, pp. 149–160.
- 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.
- 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
- 1375 reads