Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

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


Для цитирования:

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


Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
31.08.2022
Полный текст:
(downloads: 1230)
Язык публикации: 
английский
Рубрика: 
Тип статьи: 
Научная статья
УДК: 
519.17
EDN: 
IMTPKR

Forcing total outer connected monophonic number of a graph
[Форсирование общего внешне связного монофонического числа графа]

Авторы: 
Ганеcамурти Катиресан, Технологический институт Коимбатура
Лакшми Прия Шанмугам, Политехнический колледж Технологического института Коимбатура
Аннотация: 

Для связного графа $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)$ является общим внешне связным монофоническим числом графа.

Благодарности: 
Исследовательская работа первого автора была поддержана Национальным советом по высшей математике (NBHM), Департаментом атомной энергии (DAE), Правительством Индии (проект № NBHM/R.P.29/2015/Fresh/157).
Список источников: 
  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
Поступила в редакцию: 
15.09.2021
Принята к публикации: 
12.12.2021
Опубликована: 
31.08.2022