vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"vestifm-190Research ArticleМАТЕМАТИКАMATHEMATICSАЛГОРИТМИЧЕСКИЕ СВОЙСТВА СВЯЗНЫХ ОКРЕСТНОСТНЫХ МНОЖЕСТВ В ГРАФАХALGORITHMIC PROPERTIES OF CONNECTED NEIGHBOURHOOD SETS IN GRAPHSКАРТЫННИКЮ. А.KARTYNNIKY. A.kartynnik@bsu.byБелорусский государственный университетBelarusian State University201621112016033037Copyright © КАРТЫННИК Ю.А., 20162016КАРТЫННИК Ю.А.KARTYNNIK Y.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/190

В работе вводится и характеризуется класс графов, в которых каждое связное доминирующее множество является (связным) окрестностным, а также класс графов, для каждого связного порожденного подграфа которых мощности наименьшего окрестностного множества и наименьшего связного окрестностного множества совпадают. В предположении P ≠ NP доказана неаппроксимируемость за полиномиальное время с логарифмической гарантированной оценкой точности задачи о наименьшем связном окрестностном множестве в их общем подклассе – классе симплициально-расщепляемых графов.

We introduce and characterize the class of graphs in which every connected dominating set is a (connected) neighbourhood set and a class of graphs whose all connected induced subgraphs have equal minimum neighbourhood set and minimum connected neighbourhood set cardinalities. Assuming P ≠ NP, we also prove that the minimum connected neighbourhood set problem cannot be approximated within a logarithmic factor in polynomial time in their common subclass, the class of simplicial split graphs.

симплициально-расщепляемый графчисло связного доминированиясвязное окрестностное числоsimplicial split graphconnected domination numberconnected neighbourhood numberReferencesSampathkumar, E. The neighbourhood number of a graph / E. Sampathkumar, P. S. Neeralagi // Indian J. Pure Appl. Math. – 1985. – Vol. 16. – P. 126–132.Sampathkumar, E. The neighbourhood number of a graph / E. Sampathkumar, P. S. Neeralagi // Indian J. Pure Appl. Math. – 1985. – Vol. 16. – P. 126–132.Sampathkumar, E. The connected domination number of a graph / E. Sampathkumar, H. B. Walikar // J. Math. Phys. Sci. – 1979. – Vol. 13. – P. 607–613.Sampathkumar, E. The connected domination number of a graph / E. Sampathkumar, H. B. Walikar // J. Math. Phys. Sci. – 1979. – Vol. 13. – P. 607–613.Sampathkumar, E. Independent, perfect and connected neighbourhood numbers of a graph / E. Sampathkumar, P. S. Neeralagi // J. Comb. Inf. Syst. Sci. – 1994. – Vol. 19. – P. 139–145.Sampathkumar, E. Independent, perfect and connected neighbourhood numbers of a graph / E. Sampathkumar, P. S. Neeralagi // J. Comb. Inf. Syst. Sci. – 1994. – Vol. 19. – P. 139–145.Картынник, Ю. А. Доминантно-треугольные графы и графы верхних границ / Ю. А. Картынник, Ю. Л. Орлович // Докл. Нац. акад. наук Беларуси. – 2014. – Т. 58, № 1. – С. 16– 25.Картынник, Ю. А. Доминантно-треугольные графы и графы верхних границ / Ю. А. Картынник, Ю. Л. Орлович // Докл. Нац. акад. наук Беларуси. – 2014. – Т. 58, № 1. – С. 16– 25.Földes, S. Split graphs / S. Földes, P. L. Hammer // Congress. Numer. – 1978. – No. 19. – P. 311–315.Földes, S. Split graphs / S. Földes, P. L. Hammer // Congress. Numer. – 1978. – No. 19. – P. 311–315.Тышкевич, Р. И. Каноническое разложение графа, определяемого степенями его вершин / Р. И. Тышкевич, А. А. Черняк // Изв. АН БССР. Сер. физ.-мат. наук. – 1979. – Т. 5. – С. 14–26.Тышкевич, Р. И. Каноническое разложение графа, определяемого степенями его вершин / Р. И. Тышкевич, А. А. Черняк // Изв. АН БССР. Сер. физ.-мат. наук. – 1979. – Т. 5. – С. 14–26.Лекции по теории графов / В. А. Емеличев [и др.]. – М.: Наука, 1990.Лекции по теории графов / В. А. Емеличев [и др.]. – М.: Наука, 1990.Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982.Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982.Zverovich, I. E. Perfect connected-dominant graphs / I. E. Zverovich // Discuss. Math. Graph Theory. – 2003. – Vol. 23. – P. 159–162.Zverovich, I. E. Perfect connected-dominant graphs / I. E. Zverovich // Discuss. Math. Graph Theory. – 2003. – Vol. 23. – P. 159–162.

The authors declare that there are no conflicts of interest present.