Для цитирования:
Ganesamoorthy K., Lakshmi Priya S. Forcing total outer connected monophonic number of a graph [Ганеcамурти К., Лакшми Прия Ш. Форсирование общего внешне связного монофонического числа графа] // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2022. Т. 22, вып. 3. С. 278-286. DOI: 10.18500/1816-9791-2022-22-3-278-286, EDN: IMTPKR
Forcing total outer connected monophonic number of a graph
[Форсирование общего внешне связного монофонического числа графа]
Для связного графа $G = (V,E)$ с числом вершин не менее 2 подмножество $T$ минимального общего внешне связного монофонического множества $S$ графа $G$ является сильным общим внешне связным монофоническим подмножеством для $S$, если $S$ есть единственное минимальное общее внешне связное монофоническое множество, содержащее $T$. Сильное общее внешне связное монофоническое подмножество для $S$ с минимальным числом элементов есть минимальное сильное общее внешне связное монофоническое подмножество $S$. Сильное общее внешне связное монофоническое число $f_{tom}(S)$ в $G$ есть число элементов минимального сильного общего внешне связного монофонического подмножества $S$. Сильное общее внешне связное монофоническое число графа $G$ есть $f_{tom}(G) = \min\{f_{tom}(S)\}$, где минимум принимается над всеми минимальными общими внешне связными монофоническими множествами $S$ в $G$. Мы определяем его границы и находим сильное общее внешне связное монофоническое число некоторых классов графов. Показывается, что для каждой пары $a$, $b$ положительных целых с $0 \leq a < b$ и $b \geq a+4$ существует связный граф $G$ такой, что $f_{tom}(G) = a$ и $cm_{to}(G) = b$, где $cm_{to}(G)$ является общим внешне связным монофоническим числом графа.
- 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
- 1373 просмотра